An oriented coloring of planar graphs with girth at least five. (English) Zbl 1198.05069
Summary: An oriented \(k\)-coloring of an oriented graph \(G\) is a homomorphism from \(G\) to an oriented graph \(H\) of order \(k\). We prove that every oriented graph with a maximum average degree less than \(\frac{10}{3}\) and girth at least 5 has an oriented chromatic number at most 16. This implies that every oriented planar graph with girth at least 5 has an oriented chromatic number at most 16, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, and É. Sopena, “On the maximum average degree and the oriented chromatic number of a graph,” Discrete Math. 206, No.1-3, 77–89 (1999; Zbl 0932.05033)].
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C20 | Directed graphs (digraphs), tournaments |
Keywords:
oriented coloring; oriented chromatic number; planar graph; girth; discharging procedure; maximum average degreeCitations:
Zbl 0932.05033References:
| [1] | Borodin, O. V.; Ivanova, A. O., An oriented 7-colouring of planar graphs with girth at least 7, Sib. Electron. Math. Reports, 2, 222-229 (2005) · Zbl 1095.05013 |
| [2] | Borodin, O. V.; Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, 2, 239-249 (2005) · Zbl 1094.05024 |
| [3] | Borodin, O. V.; Ivanova, A. O.; Kostochka, A. V., Oriented 5-coloring of sparse plane graphs, J. Appl. Industrial Math., 1, 1, 9-17 (2007) |
| [4] | 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, 77-89 (1999) · Zbl 0932.05033 |
| [5] | Courcelle, B., The monadic second order-logic of graphs VI : On several representations of graphs by relational structures, Discrete Appl. Math., 54, 117-149 (1994) · Zbl 0809.03005 |
| [6] | Hell, P.; Nešetřil, J., (Graphs and Homomorphisms. Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28 (2004), Oxford University Press) · Zbl 1062.05139 |
| [7] | Kostochka, A. V.; Sopena, É.; Zhu, X., Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 24, 331-340 (1997) · Zbl 0873.05044 |
| [8] | Marshall, T. H., Homomorphism bounds for oriented planar graphs, J. Graph Theory, 55, 3, 175-190 (2007) · Zbl 1120.05039 |
| [9] | Nešetřil, J.; Raspaud, A., Antisymmetric flows and strong colourings of oriented graphs, Ann. Inst. Fourier, 49, 1037-1056 (1999) · Zbl 0921.05034 |
| [10] | Ochem, P., Oriented colorings of triangle-free planar graphs, Inform. Process. Lett., 92, 71-76 (2004) · Zbl 1173.68593 |
| [11] | P. Ochem, A. Pinlou, Oriented colorings of partial 2-trees. Inform. Process. Lett. (2008), in press (doi:10.1016/j.ipl.2008.04.007; P. Ochem, A. Pinlou, Oriented colorings of partial 2-trees. Inform. Process. Lett. (2008), in press (doi:10.1016/j.ipl.2008.04.007 · Zbl 1189.05063 |
| [12] | A. Pinlou, An oriented coloring of graphs with maximum average degree less than \(\frac{ 10}{ 3}\) http://hal-lirmm.ccsd.cnrs.fr/lirmm-00186693/en/; A. Pinlou, An oriented coloring of graphs with maximum average degree less than \(\frac{ 10}{ 3}\) http://hal-lirmm.ccsd.cnrs.fr/lirmm-00186693/en/ |
| [13] | Pinlou, A.; Sopena, É., Oriented vertex and arc colorings of outerplanar graphs, Inform. Process. Lett., 100, 3, 97-104 (2006) · Zbl 1185.05064 |
| [14] | Raspaud, A.; Sopena, É., Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett., 51, 4, 171-174 (1994) · Zbl 0806.05031 |
| [15] | Sopena, É., The chromatic number of oriented graphs, J. Graph Theory, 25, 191-205 (1997) · Zbl 0874.05026 |
| [16] | Sopena, É., Oriented graph coloring, Discrete Math., 229, 1-3, 359-369 (2001) · Zbl 0971.05039 |
| [17] | J. Tromp, Unpublished manuscript; J. Tromp, Unpublished manuscript |
| [18] | Wood, D. R., Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theor. Comput. Sci., 7, 1, 37-50 (2005) · Zbl 1066.68100 |
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.
