A note on list-coloring powers of graphs

DOI10.1016/J.DISC.2014.05.008MaRDI QIDQ400353zbMATH OpenOpenAlexFDO

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

Publication date 21 August 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

list coloringchoosabilitychromatic-choosablegraph powers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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$.

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

Cites work

• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• Choice Numbers of Graphs: a Probabilistic Approach
• Choosability conjectures and multicircuits
• 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)