Polynomial bounds for chromatic number VII. Disjoint holes
Maria Chudnovsky, Alex Scott, Paul D. Seymour, Sophie Spirkl · Journal of Graph Theory · 2023
Abstract A hole in a graph is an induced cycle of length at least four, and a ‐multihole in is the union of pairwise disjoint and nonneighbouring holes. It is well known that if does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer , if does not contain a ‐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.