Counterexamples to the List Square Coloring Conjecture

Abstract

Abstract The square G 2 of a graph G is the graph defined on 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 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.