Counterexamples to the List Square Coloring Conjecture
Seog‐Jin Kim, Boram Park · Journal of Graph Theory · 2014
Abstract The square G2 of a graph G is the graph defined on such that two vertices u and v are adjacent in G2 if the distance between u and v in G is at most 2. Let and be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if . It is an interesting problem to find graphs that are chromatic‐choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph G, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.