List coloring of $k$th powers (2013)

Originator(s):    Xuding Zhu (presented by D. West - REGS 2013)

Definitions: The $k$th power of a graph $G$, written $G^k$, is the graph with vertex set $V(G)$ in which distinct vertices are adjacent if the distance between them in $G$ is at most $d$. The list chromatic number of $G$, written $\chi_\ell(G)$, is the least $k$ such that whenever the vertices are given lists of size $k$, a proper coloring can be chosen in which each vertex receives a color from its list. Always $\chi_\ell(G)\ge\chi(G)$; a graph $G$ is chromatic-choosable if equality holds.

Background: The famous List Coloring Conjecture asserts that every line graph is chromatic-choosable. Equivalently, proper edge-colorings can be chosen from lists of size $\chi'(G)$ on the edges. Published first by Bollob\'as and Harris [BH], the conjecture was independently formulated earlier by Albertson and Collins in 1981 and by Vizing as early as 1975 (both unpublished).

Motivated by this conjecture, Kostochka and Woodall [KW] asked whether the square of every graph is chromatic-choosable. Kim and Park [KP] answered the question in the negative, using complete families of mutually orthogonal Latin squares to construct graphs whose squares are large complete multipartite graphs and hence are not chromatic-choosable.

Question 1: (Zhu) Does there exist a constant $k$ such that the $k$th power of every graph is chromatic-choosable? (SOLVED)

Comments: At the workshop in Jinhua where Kim announced the result of [KP], it was noticed that the construction can be modified also to create graphs $G$ such that $\chi_\ell(G^3)\gt\chi(G^3)$, so $k=3$ is not sufficient. Jon Noel reported that the question has been answered in the negative for all odd powers. Xuding Zhu reported that a group in Korea answered in the negative for all powers. A group of students at REGS 2013 did so also. Noel suggested a modified question, also posted here:

Question 2: (Noel) Does there exist a subquadratic function $f$ such that always $\chi_\ell(G^2)\le f(\chi(G^2))$?

Comment: Noel noted that it is trivial to obtained a quadratic upper bound.

[BH] B. Bollob\'as and A.J. Harris, List-colourings of graphs, Graphs Combin. 1 (1985), 115-127.
[KP] S.-J. Kim and B. Park, Counterexamples to the list square coloring conjecture, 2013 preprint, available at
[KW] A.V. Kostochka and D.R. Woodall, Choosability conjectures and multicircuits, Discrete Math. 240 (2001), no. 1-3, 123-143.