Chromatic-choosability of the power of graphs

The kkth power GkGk of a graph GG is the graph defined on V(G)V(G) such that two vertices uu and vv are adjacent in GkGk if the distance between uu and vv in GG is at most kk. Let χ(H)χ(H) and χℓ(H)χℓ(H) be the chromatic number and the list chromatic number of HH, respectively. A graph HH is called chromatic-choosable   if χℓ(H)=χ(H)χℓ(H)=χ(H). It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2013) is whether there exists a constant integer kk such that GkGk is chromatic-choosable for every graph GG.Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G2G2 is chromatic-choosable for every graph GG. Kim and Park (2014) solved Kostochka and Woodall’s conjecture in the negative by finding a family of graphs G whose squares are complete multipartite graphs with partite sets of unbounded size. In this paper, we answer Zhu’s question by showing that for every integer k≥2k≥2, there exists a graph GG such that GkGk is not chromatic-choosable. Moreover, for any fixed kk we show that the value χℓ(Gk)−χ(Gk)χℓ(Gk)−χ(Gk) can be arbitrarily large.