5-choosability equals 5-colorability on torus

Conjecture 3 · arXiv:2407.18800

arXiv Conjecture high confidence— first stated 2024-07-26

Authors: Zdeněk Dvořák, Félix Moreno Peñarrubia

Status open high confidence

The conjecture that a toroidal graph is 5-choosable if and only if it is 5-colorable remains open as of May 2026. The source paper (arXiv:2407.18800) provides partial computational evidence by enumerating minimal obstructions under a cyclic-triangle-system condition and finding no new obstructions beyond previously known ones. A wide web search found no follow-up paper resolving the full conjecture.

Reviewer notes. No follow-up paper resolving the conjecture was found. The conjecture is closely related to Thomassen's characterization of 5-colorability on the torus and is stated in the source paper as equivalent to Conjecture 2. The paper arXiv:2502.17133 (Toroidal graphs without K5- and 6-cycles, 2025) addresses 4-choosability for a restricted subclass and is not directly related.

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

Conjecture. A toroidal graph is $5$-choosable if and only if it is $5$-colorable.

Context

This conjecture is stated as equivalent to Conjecture 2 and represents the central goal of the paper: a complete choosability analogue of Thomassen's characterization of 5-colorability on the torus. The computational results of the paper, enumerating minimal obstructions under a cyclic-triangle-system condition, provide supporting evidence.

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