论文标题
从$χ$ - 到$χ_p$ and-bounded类
From $χ$- to $χ_p$-bounded classes
论文作者
论文摘要
$χ$结合的类是在星形着色和更一般的$χ_p$ - 色的背景下研究的。这导致了有限扩展类别概念的自然扩展以及这些概念的结构表征。在本文中，我们解决了与星着色界有关的两个猜想。猜想之一是被反驳的，实际上，我们确定哪种削弱是正确的。我们给出（强和弱）$χ_p$结合的类的结构特征。在途中，我们概括了木材将图的色数与其$ 1 $ ubdivision的星形数字相关联的结果。作为我们的特征的应用，除其他外，我们表明，对于每个奇数$ g> 3 $偶数均匀的图形$ g $最多包含$φ（g，ω（g））\，| g | g | $ g | $ g $ g $。
$χ$-bounded classes are studied here in the context of star colorings and more generally $χ_p$-colorings. This leads to natural extensions of the notion of bounded expansion class and to structural characterization of these. In this paper we solve two conjectures related to star coloring boundedness. One of the conjectures is disproved and in fact we determine which weakening holds true. We give structural characterizations of (strong and weak) $χ_p$-bounded classes. On the way, we generalize a result of Wood relating the chromatic number of a graph to the star chromatic number of its $1$-subdivision. As an application of our characterizations, among other things, we show that for every odd integer $g>3$ even hole-free graphs $G$ contain at most $φ(g,ω(G))\,|G|$ holes of length $g$.
