The acyclic 3-dicolouring conjecture for planar oriented graphs
The acyclic 3-dicolouring conjecture for planar oriented graphs
An oriented planar graph is an orientation of a planar graph without a pair of opposite arcs. For an oriented graph , let denote the least number of colours in a vertex-colouring whose monochromatic subdigraphs are acyclic.
Planar acyclic dichromatic conjecture. Every oriented planar graph satisfies
The paper proves the upper bound and gives a planar oriented graph with acyclic dichromatic number at least . Thus the conjectured bound would be tight if true, but its validity remains open.
Sources & referencesView supporting material
Primary source
Jørgen Bang-Jensen, Lucas Picasarri-Arrieta and Anders Yeo, “Acyclic dichromatic number of oriented graphs”, arXiv:2511.20246 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.