Chromatic-choosability of the power of graphs

The k th power G k of a graph G is the graph defined on V ( G ) such that two vertices u and v are adjacent in G k if the distance between u and v in G is at most k . Let ? ( H ) and ? ? ( H ) be the chromatic number and the list chromatic number of H , respectively. A graph H is called chromatic-choosable if ? ? ( 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 k such that G k is chromatic-choosable for every graph G .Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G 2 is chromatic-choosable for every graph G . 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 ? 2 , there exists a graph G such that G k is not chromatic-choosable. Moreover, for any fixed k we show that the value ? ? ( G k ) - ? ( G k ) can be arbitrarily large.