Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Tung Nguyen, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that for every path (Formula presented.), and every integer (Formula presented.), there is a polynomial (Formula presented.) such that every graph (Formula presented.) with chromatic number greater than (Formula presented.) either contains (Formula presented.) as an induced subgraph, or contains as a subgraph the complete (Formula presented.) -partite graph with parts of cardinality (Formula presented.). For (Formula presented.) and general (Formula presented.) this is a classical theorem of Gyárfás, and for (Formula presented.) and general (Formula presented.) this is a theorem of Bonamy et al.

Original languageEnglish (US)
JournalJournal of Graph Theory
DOIs
StateAccepted/In press - 2024

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • chromatic number
  • induced subgraphs

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph'. Together they form a unique fingerprint.

Cite this