Kostochka–Woodall list square coloring conjecture

For a graph $G$ , its square $G^2$ is the graph on $V(G)$ in which two vertices are adjacent when their distance in $G$ is at most two. Let $\chi$ and $\chi_\ell$ denote the chromatic and list chromatic numbers. Kostochka–Woodall's conjecture. For any graph $G$ ,

\chi_\ell(G^2)=\chi(G^2).

The conjecture arose from the identity between total graphs and squares of suitably subdivided graphs; the supplied text gives no general resolution.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Kostochka–Woodall List Square Coloring Conjecture
For a simple graph $G$ , define its square $G^2$ by
$V(G^2)=V(G),$
and join two vertices $x$ and $y$ when their distance in $G$ is at most $2$ . List Square Coloring Conjecture. For any graph $G$ ,
$\chi_l(G^2)=\chi(G^2).$
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).

Sources & referencesView supporting material

Primary source

Nandana K Vasudevan, K Somasundaram and N Narayanan, “List-Coloring and Chromatic-Choosability – A Dynamic Survey”, arXiv:2606.31702 (2026).

1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Equivalent formulations 1

Kostochka–Woodall List Square Coloring Conjecture

Primary source

Progress summary