Bipartite graphs whose squares are not chromatic-choosable

Seog-Jin Kim¹ ; Boram Park²

¹Konkuk University
²National Institute for Mathematical Sciences

The electronic journal of combinatorics, Tome 22 (2015) no. 1

Résumé

The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Let $\chi(H)$ and $\chi_{\ell}(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called chromatic-choosable if $\chi_{\ell} (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable.Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that $G^2$ is chromatic-choosable for every graph $G$. Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs and are not chromatic choosable. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. Hence a natural question is whether $G^2$ is chromatic-choosable or not for every bipartite graph $G$.In this paper, we give a bipartite graph $G$ such that $\chi_{\ell} (G^2) \neq \chi(G^2)$. Moreover, we show that the value $\chi_{\ell}(G^2) - \chi(G^2)$ can be arbitrarily large.

Détail

DOI : 10.37236/4343

Classification : 05C15
Mots-clés : square of graph, chromatic-choosable, list chromatic number