TY - JOUR
AU - Araújo, Júlio
AU - Cezar, Alexandre
PY - 2023/08/06
TI - On (acyclic) proper orientations and the cartesian product
JF - Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2023.230546
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/24740