Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5 -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5 -free graphs, and our result is an attempt to approach that.

Original languageEnglish (US)
Pages (from-to)845-852
Number of pages8
JournalCombinatorica
Volume43
Issue number5
DOIs
StatePublished - Oct 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • Chromatic number
  • Induced subgraphs

Fingerprint

Dive into the research topics of 'Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path'. Together they form a unique fingerprint.

Cite this