3-Choosability of Planar Graphs Forbidding C₄–C₆
Open Question on 3-Choosability for Forbidden Cycles 4–7 and 4–6 · arXiv:1508.03437
Status open high confidence
As of May 2026, both questions remain open. Planar graphs without cycles of lengths 4 to 7 are known to be 3-colorable (Borodin et al. 2005, predating the source paper), but 3-choosability for this forbidden range is unresolved. The strictly harder question—whether planar graphs without cycles of lengths 4 to 6 are 3-colorable (let alone 3-choosable)—is still wide open. A 2024 arXiv paper (2412.19059) proves DP-3-colorability for planar graphs without cycles of lengths 4, 6, or 8, which is a related but distinct forbidden set and does not resolve either question.
Cited literature (1)
-
Proves DP-3-colorability for planar graphs missing cycles of lengths 4, 6, and 8, a related but distinct forbidden set from the {4,5,6} and {4,5,6,7} cases left open by the source paper.
Reviewer notes. The 3-colorability of planar graphs without cycles of lengths 4 to 7 was established by Borodin et al. in 2005 (prior to the source paper), so the conjecture's first question is really about lifting that to 3-choosability. The conjecture's second question (3-colorability for forbidden cycles 4–6) remains completely open. No follow-up paper resolving either question was found in the literature search.
Context
After establishing 3-choosability for planar graphs without cycles of lengths 4 to 8, the authors remark that the analogous questions for shorter forbidden cycle ranges remain open. They note that the case of forbidden lengths 4 to 7 might be approachable with the methods of the paper, whereas the case 4 to 6 is wide open even for ordinary 3-colorability.
Source paper
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Zdenek Dvorak, Luke Postle · 2016-10-08
https://arxiv.org/abs/1508.03437
PDF source