The gap-cycle conjecture for 2-coloring simple planar digraphs
The gap-cycle conjecture for 2-coloring simple planar digraphs
Let be a simple planar digraph. Say that has no cycles of lengths when it contains no directed cycles whose lengths are among those integers. Gap-cycle conjecture. There exists such that every simple planar digraph without cycles of length is 2-colorable. This is presented as a relaxation of the Neumann-Lara–Škrekovski conjecture; the source says that even the original conjecture remains out of reach, so this question is open.
Sources & referencesView supporting material
Primary source
Ararat Harutyunyan and Bojan Mohar, “Planar digraphs of digirth five are 2-colorable”, arXiv:1401.2213 (2014).
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.