Kostochka–Woodall list square coloring conjecture
For a graph , its square is the graph on in which two vertices are adjacent when their distance in is at most two. Let and denote the chromatic and list chromatic numbers. Kostochka–Woodall's conjecture. For any graph ,
The conjecture arose from the identity between total graphs and squares of suitably subdivided graphs; the supplied text gives no general resolution.
Equivalent formulations
For a simple graph , define its square by
and join two vertices and when their distance in is at most . List Square Coloring Conjecture. For any graph ,
The conjecture asks whether every square of a graph is chromatic-choosable; the source gives no resolution, and this paper presents counterexamples to it.
source: Seog-Jin Kim and Boram Park, “Counterexamples to the List Square Coloring Conjecture”, arXiv:1305.2566 (2013).
References
- Nandana K Vasudevan, K Somasundaram and N Narayanan, “List-Coloring and Chromatic-Choosability – A Dynamic Survey”, arXiv:2606.31702 (2026).
Progress summary
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.