Premium
Planar Digraphs of Digirth Five Are 2‐Colorable
Author(s) -
Harutyunyan Ararat,
Mohar Bojan
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22032
Subject(s) - digraph , combinatorics , mathematics , conjecture , monochromatic color , planar , planar graph , colored , discrete mathematics , computer science , graph , physics , computer graphics (images) , materials science , optics , composite material
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.