Planar digraphs of digirth five are 2-colorable

2014/01/10 by Harutyunyan, Ararat, Mohar, Bojan · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1401.2213

Abstract

Neumann-Lara (1985) and Škrekovski conjectured that every planar digraph with digirth at least three is 2-colorable. We prove a relaxed version of this conjecture: every planar digraph of digirth at least five is 2-colorable. The result also holds in the setting of list colorings.

Cited by

• Feedback vertex sets of digraphs with bounded maximum degree
• Generalized DP-colorings of digraphs

Related

• Planar digraphs of digirth four are 2-colourable
• A Note on Graphs of Dichromatic Number 2
• Planar graphs without cycles of length 4 or 5 are (7m:2m)-DP-colorable
• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9
• A note on two conjectures that strengthen the four colour theorem