Planar Digraphs of Digirth Five Are 2‐Colorable
Ararat Harutyunyan, Bojan Mohar · Journal of Graph Theory · 2016
Abstract Neumann‐Lara (1985) and Škrekovski conjectured 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 five is 2‐colorable. The result also holds in the setting of list colorings.