A note on list-coloring powers of graphs

Abstract

Recently, Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\chi (G^k)$ unbounded and ${\chi }_{\ell }(G^k)\ge c\chi (G^k)\log \chi (G^k)$. We also provide an upper bound, ${\chi }_{\ell }(G^k)<\chi (G^k{)}^3$ for $k>1$.

5 pages, 2 figures

Cited by in corpus (1)

• A Proof of a Conjecture of Ohba