On (acyclic) proper orientations and the cartesian product - Araújo, Júlio; Cezar, Alexandre (Anais do Encontro de Teoria da Computação (ETC), 2023)
Given an orientation D of the edges of a simple graph G, the indegree of a vertex v ∈ V(G), d D (v), is the number of arcs with head in v. Such orientation induces a coloring φ(v) = d D (v) + 1 of G. We say that D is a proper k-orientation if φ is a proper (k + 1)-coloring of G. The proper orientation number of G, denoted by X(G), is the least positive integer k such that G admits a proper k-orientation. We study a variation of this problem where we consider the orientation D to be acyclic. To the best of our knowledge this is the first article considering this variation. Furthermore, we also study the parameter X for graphs obtained by the cartesian product of graphs, introducing the concept of discordant set of proper orientations, that is a set where in different orientations, the same vertex has different indegrees.