×

zbMATH — the first resource for mathematics

Oriented cliques and colorings of graphs with low maximum degree. (English) Zbl 1435.05073
Summary: An oriented clique, or oclique, is an oriented graph \(G\) such that its oriented chromatic number \(\chi_o ( G )\) equals its order \(| V ( G ) |\). We disprove a conjecture of C. Duffy et al. [Discrete Math. 342, No. 4, 959–974 (2019; Zbl 1405.05056)] by showing that for maximum degree 4, the maximum order of an oclique is equal to 12. For maximum degree 5, we prove that the maximum order of an oclique is between 16 and 18. In the same paper, C. Duffy et al. also proved that the oriented chromatic number of connected oriented graphs with maximum degree 3 and 4 is at most 9 and 69, respectively. We improve these results by showing that the oriented chromatic number of non-necessarily connected oriented graphs with maximum degree 3 (resp. 4) is at most 9 (resp. 26). The bound of 26 actually follows from a general result which determines properties for a target graph to be universal for graphs of bounded maximum degree. This generalization also allows us to get the upper bound of 90 (resp. 306, 1322) for the oriented chromatic number of graphs with maximum degree 5 (resp. 6, 7).

MSC:
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Software:
GENREG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, O. V.; Ivanova, A. O., An oriented 7-colouring of planar graphs with girth at least 7, Sib. Electron. Math. Rep., 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. Rep., 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. Ind. 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] Duffy, C., A note on colourings of connected oriented cubic graphs (Aug. 2019), arXiv e-print 1908.02883
[7] Duffy, C.; MacGillivray, G.; Sopena, É., Oriented colourings of graphs with maximum degree three and four, Discrete Math., 342, 4, 959-974 (2019) · Zbl 1405.05056
[8] Dybizbański, J.; Szepietowski, A., The oriented chromatic number of Halin graphs, Inform. Process. Lett., 114, 1-2, 45-49 (2014) · Zbl 1320.05037
[9] Esperet, L.; Ochem, P., Oriented coloring of 2-outerplanar graphs, Inform. Process. Lett., 101, 5, 215-219 (2007) · Zbl 1185.05059
[10] Klostermeyer, W. F.; MacGillivray, G., Analogs of cliques for oriented coloring, Discuss. Math. Graph Theory, 24, 373-388 (2004) · Zbl 1063.05044
[11] Kostochka, A. V.; Sopena, É.; Zhu, X., Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 24, 331-340 (1997) · Zbl 0873.05044
[12] Marshall, T. H., Homomorphism bounds for oriented planar graphs, J. Graph Theory, 55, 3, 175-190 (2007) · Zbl 1120.05039
[13] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 2, 137-146 (1999) · Zbl 0918.05062
[14] Ochem, P., Oriented colorings of triangle-free planar graphs, Inform. Process. Lett., 92, 71-76 (2004) · Zbl 1173.68593
[15] Ochem, P.; Pinlou, A., Oriented colorings of partial 2-trees, Inform. Process. Lett., 108, 2, 82-86 (2008) · Zbl 1189.05063
[16] Ochem, P.; Pinlou, A., Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs, Graphs Combin., 30, 2, 439-453 (2014) · Zbl 1298.05131
[17] Pinlou, A., An oriented coloring of planar graphs with girth at least five, Discrete Math., 309, 8, 2108-2118 (2009) · Zbl 1198.05069
[18] Pinlou, A.; Sopena, É., Oriented vertex and arc colorings of outerplanar graphs, Inform. Process. Lett., 100, 3, 97-104 (2006) · Zbl 1185.05064
[19] Raspaud, A.; Sopena, É., Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett., 51, 4, 171-174 (1994) · Zbl 0806.05031
[20] Sopena, É., The chromatic number of oriented graphs, J. Graph Theory, 25, 191-205 (1997) · Zbl 0874.05026
[21] Sopena, É., Oriented graph coloring, Discrete Math., 229, 1-3, 359-369 (2001) · Zbl 0971.05039
[22] Sopena, É., Homomorphisms and colourings of oriented graphs: An updated survey, 7th Cracow Conference on Graph Theory, Rytro 2014. 7th Cracow Conference on Graph Theory, Rytro 2014, Discrete Math., 339, 7, 1993-2005 (2016) · Zbl 1334.05046
[23] Sopena, É.; Vignal, L., A note on the chromatic number of graphs with maximum degree three (1996), LaBRI, Université Bordeaux 1
[24] Von Mrose, A., Untere Schranken für die Reichweiten von Extremalbasen fester Ordnung, Abh. Math. Semin. Univ. Hambg., 48, 1, 118-124 (1979) · Zbl 0406.10046
[25] Wood, D. R., Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theoret. 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.