KAIST Discrete Math Seminar

The square G² of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let χ(H) and χ_l(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if χ_l(H) = χ(H). It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall conjectured that χ_l(G²) = χ(G²) for every graph G, which is called List Square Coloring Conjecture. In this paper, we give infinitely many counterexamples to the conjecture. Moreover, we show that the value χ_l(G²) − χ(G²) can be arbitrary large.