Polynomial bounds for chromatic number VII. Disjoint holes
Polynomial bounds for chromatic number VII. Disjoint holes
复制标题
色数 VII 的多项式界限。
DOI：
10.1002/jgt.22987
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
图 G $G$ 中的孔是长度至少为 4 的诱导环，G $G$ 中的 k $k$‐多孔是 k $k$ 成对不相交和不相邻孔的并集。众所周知，如果 G $G$ 不包含任何空穴，那么它的色数就等于它的团数。在本文中，我们证明，对于任何整数 k ≥ 1 $k\ge 1$，如果 G $G$ 不包含 k $k$‐多孔，则其色数至多是其团数的多项式函数。我们证明，如果我们要求所有孔都是奇数或长度为四，则同样的结果成立；如果我们要求孔比任何固定常数或长度四长。这是对以多项式 χ $\chi $ 为界的图类进行更广泛研究的一部分。
Aholein a graph G $G$ is an induced cycle of length at least four, and a k $k$‐multiholein G $G$ is the union of k $k$ pairwise disjoint and nonneighbouring holes. It is well known that if G $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer k ≥ 1 $k\ge 1$, if G $G$ does not contain a k $k$‐multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially χ $\chi $‐bounded.