Counterexamples to the List Square Coloring Conjecture
Counterexamples to the List Square Coloring Conjecture
复制标题
DOI：
10.1002/jgt.21802
复制
发表时间：
2013-05
影响因子：
0.9
通讯作者：
Seog-Jin Kim;Boram Park
中科院分区：
文献类型：
--
作者：
Seog-Jin Kim;Boram Park
图G的平方G2是定义在V（G）上的图，使得如果G中的两个顶点u和v之间的距离至多为2，则两个顶点u和v在G2中相邻。设χ（H）和χ（H）分别是图H的色数和列表色数.一个图H称为色可选的，如果χ ∈（H）=χ（H）.找到色可选图是一个有趣的问题。Kostochka和Woodall（Choosability Aesthetures and multicircuits，Discrete Math.，240（2001），123-143）证明了对任意图G，χ ∈ G（G ~ 2）=χ（G ~ 2），这就是列表平方着色猜想。在这篇文章中，我们给出了无穷多个反例来证明这个猜想。此外，我们还证明了χ（G2）−χ（G2）的值可以任意大。
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 χℓ(H) be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if χℓ(H)=χ(H) . 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 χℓ(G2)=χ(G2) 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 χℓ(G2)−χ(G2) can be arbitrarily large.