Polynomial bounds for chromatic number VI. Adding a four-vertex path
Polynomial bounds for chromatic number VI. Adding a four-vertex path
复制标题
色数 VI 的多项式界限。
DOI：
10.1016/j.ejc.2023.103710
复制
发表时间：
2023
影响因子：
1
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
如果存在一个函数 f，使得该类中的每个图 G 的色数至多为 f (ω (G))，则图的遗传类是 χ 有界的，其中 ω (G) 是 G 的团数；如果 f 可以被视为多项式，则该类是多项式 χ 有界的。 Gyárfás-Sumner 猜想断言，对于每个森林 H，无 H 的图（没有 H 的诱导副本的图）的类是 χ 有界的。假设一个森林 H 是好的，如果它满足更强的性质，即无 H 的图类是多项式 χ 有界的。很少有森林被认为是好的：例如，五顶点路径的好处是开放的。事实上，甚至不知道如果森林 H 的每个组成部分都是好的，那么 H 也是好的，特别是，不知道两个四顶点路径的不相交并集是好的。这里我们展示后者（具有相应的多项式 ω (G) 16）；更一般地说，如果 H 是好的，那么 H 和四顶点路径的不相交联盟也是好的。我们还证明了一个更普遍的结果：如果 H 1 的每个分量都是好的，并且 H 2 是任何路径（或扫帚），那么既无 H 1 又无 H 2 的图类是多项式 χ 有界的。
A hereditary 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; and 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, the goodness of the five-vertex path is open. 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 (with corresponding polynomial ω (G) 16); and more generally, that if H is good then so is the disjoint union of H and a four-vertex path. We also prove an even 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.