Induced subgraphs of graphs with large chromatic number. XIII. New brooms
Induced subgraphs of graphs with large chromatic number. XIII. New brooms
复制标题
DOI：
10.1016/j.ejc.2019.103024
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
A. Scott;P. Seymour
中科院分区：
文献类型：
--
作者：
A. Scott;P. Seymour
Gyárfás（1975）和Sumner（1981）独立地证明了对于每一棵树T，不包含T作为导出子图的图类是χ-有界的，即这类图的色数由它们的团数的函数上界。这对于一般树T仍然是开放的，但是对于某些特殊的树已经被证明了。当k≥ 1时，我们假设一个长为k的扫帚是一棵树，它是从一条以a，B为端点的k-边路中，通过在B附近增加一些叶子而得到的，我们称a为它的柄。由长度为k1，...，kn的扫帚通过识别它们的柄而得到的树是（k1，...，kn）-多扫帚。Kierstead和Penrice（1994）证明了每个（1，...，1）-多丛T满足Gyárfás-Sumner猜想，Kierstead和Zhu（2004）证明了（2，...，2）-多丛T也满足Gyárfás-Sumner猜想。本文给出了一个普遍的推广，证明了每一个（1，.，1，2，.，2）-多丛满足Gyárfás-Sumner猜想。
Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is χ-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees T, but has been proved for some particular trees. For k≥ 1, let us say a broom of length k is a tree obtained from a k-edge path with ends a, b by adding some number of leaves adjacent to b, and we call a its handle. A tree obtained from brooms of lengths k 1,…, k n by identifying their handles is a (k 1,…, k n)-multibroom. Kierstead and Penrice (1994) proved that every (1,…, 1)-multibroom T satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,…, 2)-multibrooms. In this paper we give a common generalization; we prove that every (1,…, 1, 2,…, 2)-multibroom satisfies the Gyárfás-Sumner conjecture.