2013/09/04 by Kim, Seog-Jin, Kwon, Young Soo, Park, Boram
#05C10 #05C30 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1309.0888
The kth power Gk of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in Gk if the distance between u and v in G is at most k. Let χ(H) and χl(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called \em chromatic-choosable if χl (H) = χ(H). It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer k such that Gk is chromatic-choosable for every graph G. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G2 is chromatic-choosable for every graph G. Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and 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 Gk is not chromatic-choosable. Moreover, for any fixed k we show that the value χl(Gk) - χ(Gk) can be arbitrarily large.