Radius two trees specify χ-bounded classes
Radius two trees specify χ-bounded classes
复制标题
DOI：
10.1002/jgt.3190180203
复制
发表时间：
1994-03
期刊：
影响因子：
--
通讯作者：
H. Kierstead;S. Penrice
中科院分区：
文献类型：
--
作者：
H. Kierstead;S. Penrice
称一类图χ是χ-有界的，且具有χ-结合函数f，如果对所有的图G <$r，χ（G）<$f（ω（G）），其中χ（G）是图G的色数，ω（G）是图G的团数.证明了对于每一棵树T，不诱导T的图类是χ-有界的.我们表明，这是真实的情况下，T是一棵树的半径为2。© 2014 Wiley Periodicals，Inc.
A class of graphs χ is said to be χ-bounded, with χ-binding function f, if for all G ϵ Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number of G and ω(G) is the clique number of G. It has been conjectured that for every tree T, the class of graphs that do not induce T is χ-bounded. We show that this is true in the case where T is a tree of radius two. © 1994 Wiley Periodicals, Inc.