论文标题
色数VII的多项式边界。不一紧密的孔
Polynomial bounds for chromatic number VII. Disjoint holes
论文作者
论文摘要
图$ g $中的一个孔是一个至少四个的诱发周期，而$ g $中的$ k $ -multihole是一组成对的脱节和非附有漏洞。众所周知，如果$ g $不包含任何孔，则其色数等于其集团数字。在本文中，我们表明，对于任何$ k $，如果$ g $不包含$ k $ -multihole，则其色数最多是其集团数字的多项式函数。我们表明，如果我们要求所有的孔为奇数或长度四；而且，如果我们要求孔比任何固定常数或长度四的孔更长。这是对多项式$χ$结合的图形类别的更广泛研究的一部分。
A hole in a graph $G$ is an induced cycle of length at least four, and a $k$-multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any $k$, if $G$ does not contain a $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 $χ$-bounded.
