×

Planar digraphs of digirth four are 2-colorable. (English) Zbl 1371.05089

Summary: Neumann-Lara conjectured in 1985 that every planar digraph with digirth at least three is 2-colorable, meaning that the vertices can be 2-colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least four is 2-colorable.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Bokal, G. Fijavž, M. Juvan, P. M. Kayll, and B. Mohar, {\it The circular chromatic number of a digraph}, J. Graph Theory, 46 (2004), pp. 227-240. · Zbl 1041.05026
[2] L. Esperet, L. Lemoine, and F. Maffray, {\it Small feedback vertex sets in planar digraphs}, preprint, , 2016. · Zbl 1361.05058
[3] N. Golowich and D. Rolnick, {\it Acyclic subgraphs of planar digraphs}, Electron. J. Combin., 22 (2015), P3.7. · Zbl 1325.05060
[4] A. Harutyunyan and B. Mohar, {\it Planar digraphs of digirth five are \(2\)-colorable}, J. Graph Theory, 84 (2017), pp. 408-427. · Zbl 1359.05052
[5] V. Neumann-Lara, {\it The dichromatic number of a digraph}, J. Combin. Theory Ser. B, 33 (1982), pp. 265-270. · Zbl 0506.05031
[6] V. Neumann-Lara, {\it Vertex colourings in digraphs. Some problems. Seminar notes}, University of Waterloo, Waterloo, Ontario, Canada, July 8, 1985 (communicated by A. Bondy and S. Thomassé).
[7] C. Thomassen, {\it A theorem on paths in planar graphs}, J. Graph Theory, 7 (1983), pp. 169-176. · Zbl 0515.05040
[8] W. T. Tutte, {\it A theorem on planar graphs}, Trans. Amer. Math. Soc., 82 (1956), pp. 99-116. · Zbl 0070.18403
[9] W. T. Tutte, {\it Bridges and Hamiltonian circuits in planar graphs}, Aequationes Math., 15 (1977), pp. 1-33. · Zbl 0357.05039
[10] F. Wu, {\it Induced Forests in Planar Graphs}, Honors thesis, UCSD, San Diego, CA, 2010.
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.