Abstract
A hole in a graph (Figure presented.) is an induced cycle of length at least four, and a (Figure presented.) -multihole in (Figure presented.) is the union of (Figure presented.) pairwise disjoint and nonneighbouring holes. It is well known that if (Figure presented.) does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer (Figure presented.), if (Figure presented.) does not contain a (Figure presented.) -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 (Figure presented.) -bounded.
Original language | American English |
---|---|
Pages (from-to) | 499-515 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 104 |
Issue number | 3 |
DOIs | |
State | Published - Nov 2023 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Geometry and Topology
Keywords
- -boundedness
- colouring
- induced subgraph