Chromatic-choosability of the power of graphs
Chromatic-choosability of the power of graphs
复制标题
DOI：
10.1016/j.dam.2014.08.004
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Seog-Jin Kim;Young Soo Kwon;Boram Park
中科院分区：
文献类型：
--
作者：
Seog-Jin Kim;Young Soo Kwon;Boram Park
图G的k次幂Gk是定义在V（G）上的图，使得如果G中的两个顶点u和v之间的距离至多为k，则两个顶点u和v在Gk中相邻.设χ（H）和χ（H）分别为H的色数和列表色数.如果图H的色数为χ 2（H）= χ 2（H），则称图H是色可选的.寻找可色选的图是一个有趣的问题。Xuding Zhu（2013）提出的一个自然问题是：是否存在一个常数k使得G k对每个图G都是色选的。受列表全染色猜想的启发，Kostochka和Woodall（2001）提出了一个问题：是否对每个图G，G2都是色可选的。Kim和Park（2014）通过找到一个图族G，其平方是具有无限大小的部集的完全多部图，解决了Kostochka和Woodall的猜想。在本文中，我们通过证明对任意整数k≥ 2，存在一个图G使得Gk不是色选的，从而回答了Zhu的问题.此外，对于任何固定的k，我们证明了值χ ∈（G k）− χ（G k）可以任意大。
The k th power G k of a graph G is the graph defined on V (G) such that two vertices u and v are adjacent in G k if the distance between u and v in G is at most k. Let χ (H) and χ ℓ (H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if χ ℓ (H)= χ (H). It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2013) is whether there exists a constant integer k such that G k is chromatic-choosable for every graph G. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G 2 is chromatic-choosable for every graph G. Kim and Park (2014) solved Kostochka and Woodall’s conjecture in the negative by finding a family of graphs G whose squares are complete multipartite graphs with partite sets of unbounded size. In this paper, we answer Zhu’s question by showing that for every integer k≥ 2, there exists a graph G such that G k is not chromatic-choosable. Moreover, for any fixed k we show that the value χ ℓ (G k)− χ (G k) can be arbitrarily large.