Claw-free graphs VI. Colouring
Claw-free graphs VI. Colouring
复制标题
无爪图VI。
DOI：
10.1016/j.jctb.2010.04.005
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
M. Chudnovsky;P. Seymour
本文证明了：如果G是一个连通的无爪图，有三个两两互不相邻的顶点，色数为χ，团数为ω，则χ ∈ 2ω，G的补图也是如此.我们还证明了G的选择数至多为2ω，除非可能是由Schläfli图的一个子图通过复制顶点得到G.最后，我们证明了常数2在所有情况下都是最好的。
In this paper we prove that if G is a connected claw-free graph with three pairwise non-adjacent vertices, with chromatic number χ and clique number ω, then χ⩽2ω and the same for the complement of G. We also prove that the choice number of G is at most 2ω, except possibly in the case when G can be obtained from a subgraph of the Schläfli graph by replicating vertices. Finally, we show that the constant 2 is best possible in all cases.