×

Oriented colorings of 2-outerplanar graphs. (English) Zbl 1185.05059

Summary: A graph \(G\) is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph \(H\) is defined as the minimum order of an oriented graph \(H'\) such that H has a homomorphism to \(H'\). In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament \(QR_{67}\), which implies that their (strong) oriented chromatic number is at most 67.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boiron, P.; Sopena, E.; Vignal, L., Acyclic improper colourings of graphs, J. Graph Theory, 32, 97-107 (1999) · Zbl 0929.05031
[2] Fried, E., On homogeneous tournaments, Combin. Theory Appl., II, 467-476 (1970) · Zbl 0215.33704
[3] Hackmann, A.; Kemnitz, A., List edge colorings of outerplanar graphs, Ars Combin., 60, 181-185 (2001) · Zbl 1071.05525
[4] Nešetřil, J.; Raspaud, A., Antisymmetric flows and strong colorings of oriented planar graphs, Ann. Inst. Fourier, 49, 3, 1037-1056 (1999) · Zbl 0921.05034
[5] Ochem, P., Oriented colorings of triangle-free planar graphs, Inform. Process. Lett., 92, 2, 71-76 (2004) · Zbl 1173.68593
[6] Ochem, P., Ph.D. thesis, Université Bordeaux 1, 2005
[7] Raspaud, A.; Sopena, E., Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett., 51, 4, 171-174 (1994) · Zbl 0806.05031
[8] Sopena, E., Oriented graph coloring, Discrete Math., 229, 1-3, 359-369 (2001) · Zbl 0971.05039
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.