Polynomial bounds for chromatic number VII. Disjoint holes

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)499-515
Number of pages17
JournalJournal of Graph Theory
Volume104
Issue number3
DOIs
StatePublished - Nov 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology

Keywords

  • -boundedness
  • colouring
  • induced subgraph

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number VII. Disjoint holes'. Together they form a unique fingerprint.

Cite this