Planar digraphs of digirth four are 2-colourable

2016/06/20 by Zhentao Li, Li, Zhentao, Bojan Mohar +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1606.06114

openalex publication_date 2016/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

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

Related

• Planar digraphs of digirth five are 2-colorable
• A Note on Graphs of Dichromatic Number 2
• A note on two conjectures that strengthen the four colour theorem
• Mathematical Proofs of Two Conjectures: The Four Color Problem and The Uniquely 4-colorable Planar Graph
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable