Neumann–Lara's acyclic 2-coloring conjecture for planar digraphs
A digraph is a directed graph, and an acyclic set is a vertex set inducing no directed cycle. A vertex-partition into two acyclic sets is a partition of all vertices into two such sets.
Neumann–Lara's conjecture. Every planar digraph of digirth at least can be vertex-partitioned into two acyclic sets.
The source states that this conjecture remains open in general, although Li and Mohar established it for planar digraphs of digirth at least .
References
Primary source
Simon Dreyer, Alexandre Pinlou and Petru Valicov, “Feedback vertex sets of planar digraphs with fixed digirth”, arXiv:2605.12279 (2026).
Additional references
3 papers in this index state this conjecture (2015–2026). The statement above is taken from the most recent of them; the others are arXiv:1712.06143, arXiv:1504.06726.
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
No solutions have been posted yet.