Kostochka–Woodall conjecture on the choice number of graph squares

Let GG be a simple graph. Its square G2G^2 is the graph on V(G)V(G) in which two vertices are adjacent when their distance in GG is at most two. Let χ(G2)\chi(G^2) denote its chromatic number and let χl(G2)\chi_l(G^2) denote its choice number, the least kk such that every assignment of lists of kk colors to the vertices admits a proper list-coloring.

Kostochka–Woodall conjecture.

χl(G2)=χ(G2).\chi_l(G^2)=\chi(G^2).

This asserts that every graph square is chromatic-choosable. The conjecture is presented as a motivation for the paper's list-coloring results, but no resolution is given in the supplied text.

Sources & referencesView supporting material

Primary source

Daniel W. Cranston, Rok Erman and Riste Škrekovski, “Choosability of the square of a planar graph with maximum degree four”, arXiv:1303.5156 (2013).

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.

Solutions 0

No solutions have been posted yet.