Correspondence chromatic number planar graphs C₄–C₈-free

Informal Conjecture on Correspondence Chromatic Number of Planar Graphs Without Cycles 4–8 · arXiv:1508.03437

arXiv Informal medium confidence— first stated 2016-10-08

Authors: Zdenek Dvorak, Luke Postle

Status solved high confidence

Jin, Kang, and Zhu (arXiv:2412.19059, December 2024) proved the stronger Theorem 1.4: every planar graph with no cycle of length 4, 6, or 8 is DP-3-colorable. Since any planar graph without cycles of lengths 4 to 8 is a special case (having no 4-, 6-, or 8-cycles), the conjecture of Dvořák and Postle follows as an immediate corollary. The paper explicitly identifies this as resolving the conjecture from arXiv:1508.03437, describing it as a ‘more natural and stronger claim’ that such graphs are DP-3-colorable without the consistency assumption.

Cited literature (1)

proof Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable (2024)

Ligang Jin, Yingli Kang, Xuding Zhu · arXiv preprint · arXiv:2412.19059

Proves that every planar graph with no cycle of length 4, 6, or 8 is DP-3-colorable (Theorem 1.4), which is strictly stronger than the conjecture and implies it as a corollary; the paper explicitly cites the Dvořák–Postle conjecture from 1508.03437.

Reviewer notes. The conjecture is resolved as a corollary of a strictly stronger theorem proved in arXiv:2412.19059. The stronger result only requires excluding cycles of lengths 4, 6, and 8 (not all five lengths 4–8), making it a genuine strengthening rather than merely a proof of the original statement.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Every planar graph $G$ without cycles of lengths 4 to 8 has correspondence chromatic number at most 3, i.e., $G$ is $C$-colorable for every 3-correspondence assignment $C$ (without the additional assumption of consistency on closed walks of length 3).

Context

Theorem 6 is proved only for 3-correspondence assignments that are consistent on every closed walk of length 3, a restriction needed to carry out the main reduction. The authors remark that they do not know any counterexample to the stronger claim that the full correspondence chromatic number is at most 3.

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