**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.

**References:**

[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 http://arxiv.org/abs/1305.2566.

[KW] A.V. Kostochka and D.R. Woodall,
Choosability conjectures and multicircuits,
Discrete Math. 240 (2001), no. 1-3, 123-143.