Counterexamples to the List Square Coloring Conjecture |
| |
Authors: | Seog‐Jin Kim Boram Park |
| |
Affiliation: | 1. DEPARTMENT OF MATHEMATICS EDUCATION, KONKUK UNIVERSITY, SEOUL, KOREA;2. NATIONAL INSTITUTE FOR MATHEMATICAL SCIENCES, DAEJEON, KOREA |
| |
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. |
| |
Keywords: | square of graph chromatic number list chromatic number 05C15 |
|
|