Boram Park (박보람), Counterexamples to the List Square Coloring Conjecture

Counterexamples to the List Square Coloring Conjecture
Boram Park
Optimization and Its Application Research Team
2013/10/16 Wednesday 4PM-5PM
ROOM 1409
The square G2 of a graph G is the graph defined on V(G) 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 χ(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(G2) = χ(G2) 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(G2) − χ(G2) can be arbitrary large.


Comments are closed.