Counterexamples to the List Square Coloring Conjecture

2013/10/16 Wednesday 4PM-5PM

ROOM 1409

ROOM 1409

The square

*G*^{2}of a graph*G*is the graph defined on*V(G)*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 χ(*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*^{2}) = χ(*G*^{2}) 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*^{2}) − χ(*G*^{2}) can be arbitrary large.Tags: 박보람