Oriented total-coloring of oriented graphs. (English) Zbl 07898303
Summary: A proper \(n\)-coloring of a graph \(G\) is an assignment of colors from \(\{1, \ldots, n \}\) to its vertices such that no two adjacent vertices get assigned the same color. The chromatic number of \(G\), denoted by \(\chi(G)\), refers to the smallest \(n\) such that \(G\) admits a proper \(n\)-coloring. This notion naturally extends to edge-colorings (resp. total-colorings) when edges (resp. both vertices and edges) are to be colored, and this provides other parameters of \(G\): its chromatic index \(\chi^\prime(G)\) and its total chromatic number \(\chi''(G)\).
These coloring notions are among the most fundamental ones of the graph coloring theory. As such, they gave birth to hundreds of studies dedicated to several of their aspects, including generalizations to more general structures such as oriented graphs. They include notably the notions of oriented \(n\)-colorings and oriented \(n\)-arc-colorings, which stand as natural extensions of their undirected counterparts, and which have been receiving increasing attention.
Our goal is to introduce a missing piece in this line of work, namely the oriented counterparts of proper \(n\)-total-colorings and total chromatic number. We first define these notions and show that they share properties and connections with oriented (arc) colorings that are reminiscent of those shared by their undirected counterparts. We then focus on understanding the oriented total chromatic number of particular types of oriented graphs, such as oriented forests, cycles, and some planar graphs. Finally, we establish a full complexity dichotomy for the problem of determining whether an oriented graph is totally \(k\)-colorable.
Throughout this work, each of our results is compared to what is known regarding the oriented chromatic number and oriented chromatic index. We also disseminate some directions for further research on the oriented total chromatic number.
These coloring notions are among the most fundamental ones of the graph coloring theory. As such, they gave birth to hundreds of studies dedicated to several of their aspects, including generalizations to more general structures such as oriented graphs. They include notably the notions of oriented \(n\)-colorings and oriented \(n\)-arc-colorings, which stand as natural extensions of their undirected counterparts, and which have been receiving increasing attention.
Our goal is to introduce a missing piece in this line of work, namely the oriented counterparts of proper \(n\)-total-colorings and total chromatic number. We first define these notions and show that they share properties and connections with oriented (arc) colorings that are reminiscent of those shared by their undirected counterparts. We then focus on understanding the oriented total chromatic number of particular types of oriented graphs, such as oriented forests, cycles, and some planar graphs. Finally, we establish a full complexity dichotomy for the problem of determining whether an oriented graph is totally \(k\)-colorable.
Throughout this work, each of our results is compared to what is known regarding the oriented chromatic number and oriented chromatic index. We also disseminate some directions for further research on the oriented total chromatic number.
References:
| [1] | Borodin, O. V., On acyclic colorings of planar graphs, Discrete Math., 25, 3, 211-236, 1979 · Zbl 0406.05031 |
| [2] | Borodin, O. V.; Kostochka, A. V.; Nešetřil, J.; Raspaud, A.; Sopena, É., On universal graphs for planar oriented graphs of a given girth, Discrete Math., 188, 1-3, 73-85, 1998 · Zbl 0956.05041 |
| [3] | Borodin, O. V.; Kostochka, A. V.; Nešetřil, J.; Raspaud, A.; Sopena, É., On the maximum average degree and the oriented chromatic number of a graph, Discrete Math., 206, 1-3, 77-89, 1999 · Zbl 0932.05033 |
| [4] | Borodin, O. V.; Fon-Der-Flaass, D.; Kostochka, A. V.; Raspaud, A.; Sopena, É., On deeply critical oriented graphs, J. Comb. Theory, Ser. B, 81, 1, 150-155, 2001 · Zbl 1025.05024 |
| [5] | Borodin, O. V.; Kim, S.-J.; Kostochka, A. V.; West, D. B., Homomorphisms from sparse graphs with large girth, J. Comb. Theory, Ser. B, 90, 1, 147-159, 2004 · Zbl 1033.05037 |
| [6] | Courcelle, B., The monadic second order logic of graphs vi: on several representations of graphs by relational structures, Discrete Appl. Math., 54, 2, 117-149, 1994 · Zbl 0809.03005 |
| [7] | Duffy, C., Colourings of oriented connected cubic graphs, Discrete Math., 343, 10, Article 112021 pp., 2020 · Zbl 1475.05065 |
| [8] | Kostochka, A. V.; Sopena, É.; Zhu, X., Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 24, 331-340, 1997 · Zbl 0873.05044 |
| [9] | Marshall, T., Homomorphism bounds for oriented planar graphs, J. Graph Theory, 55, 3, 175-190, 2007 · Zbl 1120.05039 |
| [10] | Marshall, T. H., On oriented graphs with certain extension properties, Ars Comb., 120, 223-236, 2015 · Zbl 1349.05120 |
| [11] | Nandy, A.; Sen, S.; Sopena, É., Outerplanar and planar oriented cliques, J. Graph Theory, 82, 2, 165-193, 2016 · Zbl 1339.05081 |
| [12] | Ochem, P.; Pinlou, A.; Sopena, E., On the oriented chromatic index of oriented graphs, J. Graph Theory, 57, 4, 313-332, 2008 · Zbl 1147.05032 |
| [13] | Raspaud, A.; Sopena, É., Good and semi-strong colorings of oriented planar graphs, Inf. Process. Lett., 51, 4, 171-174, 1994 · Zbl 0806.05031 |
| [14] | Sen, S., A contribution to the theory of graph homomorphisms and colorings, 2014, Bordeaux University: Bordeaux University France, PhD thesis |
| [15] | Sopena, É., The chromatic number of oriented graphs, J. Graph Theory, 25, 3, 191-205, 1997 · Zbl 0874.05026 |
| [16] | Sopena, É., Complete oriented colourings and the oriented achromatic number, Discrete Appl. Math., 173, 102-112, 2014 · Zbl 1298.05135 |
| [17] | Sopena, É., Homomorphisms and colourings of oriented graphs: an updated survey, Discrete Math., 339, 7, 1993-2005, 2016 · Zbl 1334.05046 |
| [18] | Tuza, Z.; Voigt, M., Oriented list colorings of graphs, J. Graph Theory, 36, 4, 217-229, 2001 · Zbl 0991.05046 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
