Chromatic-choosability of the power of graphs

DOI10.1016/J.DAM.2014.08.004zbMATH Open1303.05064arXiv1309.0888OpenAlexW2018588622MaRDI QIDQ476310FDOQ476310

Authors: Seog-Jin Kim, Young Soo Kwon, Boram Park

Publication date: 28 November 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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

c h i (H)

and

c h i_{l} (H)

be the chromatic number and the list chromatic number of

H

, respectively. A graph

H

is called {em chromatic-choosable} if

c h i_{l} (H) = c h i (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

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 (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