Polynomial bounds for chromatic number II: Excluding a star-forest

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

Abstract

The Gyárfás–Sumner conjecture says that for every forest (Formula presented.), there is a function (Formula presented.) such that if (Formula presented.) is (Formula presented.) -free then (Formula presented.) (where (Formula presented.) are the chromatic number and the clique number of (Formula presented.)). Louis Esperet conjectured that, whenever such a statement holds, (Formula presented.) can be chosen to be a polynomial. The Gyárfás–Sumner conjecture is only known to be true for a modest set of forests (Formula presented.), and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when (Formula presented.) is a five-vertex path. Here we prove Esperet's conjecture when each component of (Formula presented.) is a star.

Original languageEnglish (US)
Pages (from-to)318-322
Number of pages5
JournalJournal of Graph Theory
Volume101
Issue number2
DOIs
StatePublished - Oct 2022

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • Gyárfás–Sumner conjecture
  • chromatic number
  • colouring
  • induced subgraph
  • χ-boundedness

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number II: Excluding a star-forest'. Together they form a unique fingerprint.

Cite this