Planar digraphs of digirth five are 2-colorable

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.

25 pages