| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4646889 | Discrete Mathematics | 2014 | 5 Pages |
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 kth 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 Ï(Gk) unbounded and Ïâ(Gk)â¥cÏ(Gk)logÏ(Gk). We also provide an upper bound, Ïâ(Gk)<Ï(Gk)3 for k>1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nicholas Kosar, Sarka Petrickova, Benjamin Reiniger, Elyse Yeager,