Radius Three Trees in Graphs with Large Chromatic Number
Radius Three Trees in Graphs with Large Chromatic Number
复制标题
DOI：
10.1137/s0895480198339869
复制
发表时间：
2004-04
期刊：
影响因子：
--
通讯作者：
H. Kierstead;Yingxian Zhu
中科院分区：
文献类型：
--
作者：
H. Kierstead;Yingxian Zhu
一个图类$\Gamma$是$\chi$-有界的，如果存在一个函数$f$使得对所有的图$G \in \Gamma$，$\chi$表示色数，$\omega$表示团数，$\chi \left（G\right）\leq f \left（\omega \left（G\right）\right）$。Gyarfas和Sumner独立地证明了，对于任何树T，由不包含T作为导出子图的图组成的类${\rm Forb} \left（T\right）$是$\chi$-有界的。第一作者和Penrice证明了这个猜想对任何半径为2的树都是正确的。在这里，我们使用的工作，几个作者表明，猜想是真实的半径3树半径2树，使每一个边缘的细分相邻的根。这些是唯一的树半径大于2，除了细分的恒星，其中猜想是已知的是真实的。
A class $\Gamma$ of graphs is $\chi$-bounded if there exists a function $f$ such that $\chi \left(G\right) \leq f \left(\omega \left(G\right) \right)$ for all graphs $G \in \Gamma$, where $\chi$ denotes chromatic number and $\omega$ denotes clique number. Gyarfas and Sumner independently conjectured that, for any tree T, the class ${\rm Forb} \left(T\right)$, consisting of graphs that do not contain T as an induced subgraph, is $\chi$-bounded. The first author and Penrice showed that this conjecture is true for any radius two tree. Here we use the work of several authors to show that the conjecture is true for radius three trees obtained from radius two trees by making exactly one subdivision in every edge adjacent to the root. These are the only trees with radius greater than two, other than subdivided stars, for which the conjecture is known to be true.