Polynomial bounds for chromatic number VII. Disjoint holes
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 14, 2023
- Source ID
- 10.1002/jgt.22987
Entities
People
- Alexander David Scott
- Maria Chudnovsky
- Paul Seymour
- Sophie Spirkl
Organizations
- Air Force Office of Scientific Research
- Engineering and Physical Sciences Research Council
- National Science Foundation
- Natural Sciences and Engineering Research Council
- Princeton University
- University of Oxford
- University of Waterloo