Konkuk University

Room 3433

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 with partite sets of unbounded size. 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. On the other hand, the counterexamples to the List Square Coloring Conjecture are not 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. This is joint work with Boram Park.

Tags: 김석진