5-choosability equals 6-criticality on torus
Conjecture 2 · arXiv:2407.18800
Status open high confidence
The conjecture that a graph drawn on the torus is critical for 5-choosability if and only if it is 6-critical remains open. The source paper (arXiv:2407.18800) establishes this equivalence under the additional assumption that there exists a cyclic system of non-contractible triangles around the torus with consecutive triangles at distance at most four, with K_7 as the sole exceptional case handled separately. A wide web search covering Dvořák's publication record through 2026 found no follow-up paper proving or disproving the full conjecture.
Reviewer notes. The HTML version of the paper labels the criticality formulation as 'Conjecture 3 (equivalent formulation)' while 'Conjecture 2' states the equivalent 'A toroidal graph is 5-choosable if and only if it is 5-colorable'; these are logically equivalent statements. The paper's Theorem 1 resolves a special case (cyclic non-contractible triangle systems of spacing ≤ 4). No resolution of the full conjecture was found in the indexed literature as of May 2026.
Context
Theorem 1 establishes this result under the additional assumption that there exists a cyclic system of non-contractible triangles around the torus with consecutive triangles at distance at most four. The authors verified that $K_7$ is the only graph critical for 5-list coloring but not for 5-choosability satisfying the assumptions of Theorem 1, and believe the cyclic system assumption can be dropped entirely.
Source paper
Towards Characterization of 5-List-Colorability of Toroidal Graphs
Zdeněk Dvořák, Félix Moreno Peñarrubia · 2024-07-26
https://arxiv.org/abs/2407.18800