Polynomial bounds for chromatic number VII. Disjoint holes.
Abstract
A hole in a graph G is an induced cycle of length at least four, and a k-multihole in G is the union of k pairwise disjoint and nonneighbouring 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 integer k>1, 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 x-bounded.
Collections
Cite this version of the work
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl
(2023).
Polynomial bounds for chromatic number VII. Disjoint holes.. UWSpace.
http://hdl.handle.net/10012/19494
Other formats
The following license files are associated with this item: