zbMATH — the first resource for mathematics

A note on list-coloring powers of graphs. (English) Zbl 1298.05123
Summary: Recently, S.-J. Kim and B. Park [“Counterexamples to the list square coloring conjecture”, J. Graph Theory (to appear; doi:10.1002/jgt.21802)] 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) \geq 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\).

05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv
[1] Alon, Noga, Choice numbers of graphs: a probabilistic approach, Combin. Probab. Comput., 1, 2, 107-114, (1992) · Zbl 0793.05076
[2] (Colbourn, Charles J.; Dinitz, Jeffrey H., The CRC Handbook of Combinatorial Designs, CRC Press Series on Discrete Mathematics and its Applications, (1996), CRC Press Boca Raton, FL) · Zbl 0836.00010
[3] Seog-Jin Kim, Young Soo Kwon, Boram Park, Chromatic-choosability of the power of graphs. arXiv:1309.0888. · Zbl 1303.05064
[4] Seog-Jin Kim, Boram Park, Counterexamples to the list square conjecture, J. Graph Theory, in press. arXiv:1305.2566.
[5] Kostochka, Alexandr V.; Woodall, Douglas R., Choosability conjectures and multicircuits, Discrete Math., 240, 1-3, 123-143, (2001) · Zbl 0989.05041
[6] Jonathan A. Noel, Choosability of graph powers, August 2013. http://www.openproblemgarden.org/op/choosability_of_graph_powers.
[7] Xuding Zhu, personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.