A note on list-coloring powers of graphs

DOI10.1016/J.DISC.2014.05.008zbMATH Open1298.05123arXiv1309.7705OpenAlexW1979646850MaRDI QIDQ400353FDOQ400353

Authors: Nicholas Kosar, Šárka Petříčková, Benjamin Reiniger, Elyse Yeager 

Publication date: 21 August 2014

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

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 $ch{i}_{ell}(G^k)geqcchi(G^k)logchi(G^k)$. We also provide an upper bound, $ch{i}_{ell}(G^k)<chi(G^k{)}^3$ for $k>1$.

Full work available at URL: https://arxiv.org/abs/1309.7705

Recommendations

• Chromatic-choosability of the power of graphs
• Counterexamples to the list square coloring conjecture
• Bipartite graphs whose squares are not chromatic-choosable
• Coloring graphs from lists with bounded size of their union
• List Coloring with a Bounded Palette

zbMATH Keywords

list coloringchoosabilitychromatic-choosablegraph powers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Choosability conjectures and multicircuits
• Choice Numbers of Graphs: a Probabilistic Approach
• Chromatic-choosability of the power of graphs

Cited In (7)

• Chromatic-choosability of the power of graphs
• Towards a version of Ohba's conjecture for improper colorings
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• Bipartite graphs whose squares are not chromatic-choosable
• Counterexamples to the list square coloring conjecture
• A proof of a conjecture of Ohba
• Choosability of powers of circuits

This page was built for publication: A note on list-coloring powers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400353)