Bipartite graphs whose squares are not chromatic-choosable (Q2260619)

Summary: 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, \textit{A. V. Kostochka} and \textit{D. R. Woodall} [Discrete Math. 240, No. 1--3, 123--143 (2001; Zbl 0989.05041)] proposed the List Square Coloring Conjecture which states that \(G^2\) is chromatic-choosable for every graph \(G\). Recently, \textit{S.-J. Kim} and \textit{B. Park} [J. Graph Theory 78, No. 4, 239--247 (2015; Zbl 1309.05075)] 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.