The gap-cycle conjecture for 2-coloring simple planar digraphs

At least 11 years old · documented by

Let DD be a simple planar digraph. Say that DD has no cycles of lengths 4,…,k4,\dots,k when it contains no directed cycles whose lengths are among those integers. Gap-cycle conjecture. There exists kk such that every simple planar digraph without cycles of length 4,…,k4,\dots,k 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.

References

Primary source

Ararat Harutyunyan and Bojan Mohar, “Planar digraphs of digirth five are 2-colorable”, arXiv:1401.2213 (2014).

Progress summary

Never refreshed

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.