On (acyclic) proper orientations and the cartesian product
Resumo
Given an orientation D of the edges of a simple graph G, the indegree of a vertex v ∈ V(G), dD(v), is the number of arcs with head in v. Such orientation induces a coloring φ(v) = dD(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.
Referências
A. Ahadi, A. Dehghan, and M. Saghafian, Is there any polynomial upper bound for the universal labeling of graphs?, Journal of Combinatorial Optimization 34 (2017), no. 3, 760–770.
J. Araujo, A. Cezar, C. V. G. C. Lima, V. dos Santos, and A. Silva, On the proper orientation number of chordal graphs, Theoretical Computer Science 888 (2021), 117–132.
J. Araujo, N. Cohen, S. F. de Rezende, F. Havet, and P.F.S. Moura, On the proper orientation number of bipartite graphs, Theoretical Computer Science 566 (2015), 59–75.
J. Araujo, F. Havet, C. Linhares Sales, and A. Silva, Proper orientation of cacti, Theoretical Computer Science 639 (2016), 14–25.
J. Araújo, C. L. Sales, I. Sau, and A. Silva, Weighted proper orientations of trees and graphs of bounded treewidth, Theoretical Computer Science 771 (2019), 39–48.
J. Bang-Jensen and G. Z. Gutin, Digraphs: theory, algorithms and applications, Springer Science & Business Media, 2008.
Mieczysław Borowiecki, Jarosław Grytczuk, and Monika Pilśniak, Coloring chip configurations on graphs and digraphs, Information Processing Letters 112 (2012), no. 1-2, 1–4.
A. Dehghan and F. Havet, On the semi-proper orientations of graphs, Discrete Applied Mathematics 296 (2021), 9–25.
Ali Dehghan, On the in–out–proper orientations of graphs, Discrete Applied Mathematics 302 (2021), 129–138.
Michał Karoński, Tomasz Łuczak, and Andrew Thomason, Edge weights and vertex colours, Journal of Combinatorial Theory Series B 91 (2004), no. 1, 151–157.
D. B. West, Introduction to graph theory, Vol. 2, Prentice hall Upper Saddle River, 2001.
