论文标题
色数VI的多项式边界。添加四个vertex路径
Polynomial bounds for chromatic number VI. Adding a four-vertex path
论文作者
论文摘要
如果有一个函数$ f $，则一类图形为$χ$ cound，使得同类中的每个图$ g $最多都有$ f（ω（g））$，其中$ω（g）$是$ g $的集团;如果可以将$ f $视为多项式，则该类是多项式$χ$结合的。 Gyárfás-Sumner的猜想断言，对于每个森林$ h $，$ h $ free Graphs（无诱导副本为$ h $）的类别为$χ$ bounded。让我们说，如果满足$ h $ free图的类别是多项式$χ$结合的较强的财产，那么它是一个很好的森林$ H $。 众所周知，很少有森林是很好的：例如，它是针对五个vertex路径开放的。确实，甚至还不知道，如果$ h $的每个组成部分都不错，那么$ h $是好的，尤其是，众所周知，两种四个vertex路径的脱节结合是好的。在这里，我们表明后者，更普遍地表明，如果$ h $很好，那么$ h $和四个vertex路径的脱节也是如此。我们还证明了一个更普遍的结果：如果$ H_1 $的每个组件都不错，而$ H_2 $是任何路径（或扫帚），则均为$ h_1 $ - free和$ h_2 $的图形类别是多样地$χ$ b的。
A class of graphs is $χ$-bounded if there is a function $f$ such that every graph $G$ in the class has chromatic number at most $f(ω(G))$, where $ω(G)$ is the clique number of $G$; the class is polynomially $χ$-bounded if $f$ can be taken to be a polynomial. The Gyárfás-Sumner conjecture asserts that, for every forest $H$, the class of $H$-free graphs (graphs with no induced copy of $H$) is $χ$-bounded. Let us say a forest $H$ is good if it satisfies the stronger property that the class of $H$-free graphs is polynomially $χ$-bounded. Very few forests are known to be good: for example, it is open for the five-vertex path. Indeed, it is not even known that if every component of a forest $H$ is good then $H$ is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter, and more generally, that if $H$ is good then so is the disjoint union of $H$ and a four-vertex path. We also prove a more general result: if every component of $H_1$ is good, and $H_2$ is any path (or broom) then the class of graphs that are both $H_1$-free and $H_2$-free is polynomially $χ$-bounded.
