Chromatic-choosability of the power of graphs

DOI10.1016/J.DAM.2014.08.004MaRDI QIDQ476310zbMATH OpenOpenAlexFDO

Authors Seog-Jin Kim, Young Soo Kwon, Boram Park

Publication date 28 November 2014

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

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

zbMATH Keywords

list coloringchromatic choosabilitypower of graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The $k$th power $G^k$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^k$ if the distance between $u$ and $v$ in $G$ is at most $k$. Let $chi(H)$ and $ch{i}_l(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called {em chromatic-choosable} if $ch{i}_l(H)=chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer $k$ such that $G^k$ is chromatic-choosable for every graph $G$. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether $G^2$ is chromatic-choosable for every graph $G$. Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and unbounded size. In this paper, we answer Zhu's question by showing that for every integer $kgeq2$, there exists a graph $G$ such that $G^k$ is not chromatic-choosable. Moreover, for any fixed $k$ we show that the value $ch{i}_l(G^k)-chi(G^k)$ can be arbitrarily large.

Recommendations

• A note on list-coloring powers of graphs
• Bipartite graphs whose squares are not chromatic-choosable
• Counterexamples to the list square coloring conjecture
• Choosability of powers of circuits
• On chromatic‐choosable graphs

Cites work

• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• A note on list-coloring powers of graphs
• A proof of a conjecture of Ohba
• Choice Numbers of Graphs: a Probabilistic Approach
• Choice number of 3-colorable elementary graphs
• Choosability conjectures and multicircuits
• Counterexamples to the list square coloring conjecture
• List edge and list total colourings of multigraphs
• On chromatic‐choosable graphs
• On the choosability of complete multipartite graphs with part size three
• The list chromatic index of a bipartite multigraph

Cited in

(8)

• Strong list-chromatic index of subcubic graphs
• Coloring Powers of Chordal Graphs
• A note on list-coloring powers 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
• Choosability of powers of circuits
• Bipartite graphs whose squares are not chromatic-choosable
• Counterexamples to the list square coloring conjecture

This page was built for publication: Chromatic-choosability of the power of graphs

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