Polynomial bounds for chromatic number. III. Excluding a double star

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

A “double star” is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star (Formula presented.), there is a function (Formula presented.) such that if (Formula presented.) does not contain (Formula presented.) as an induced subgraph then (Formula presented.) (where (Formula presented.) are the chromatic number and the clique number of (Formula presented.)). Here we prove that (Formula presented.) can be chosen to be a polynomial.

Original languageEnglish (US)
Pages (from-to)323-340
Number of pages18
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
  • chi-boundedness
  • induced subgraph

Fingerprint

Dive into the research topics of 'Polynomial bounds for chromatic number. III. Excluding a double star'. Together they form a unique fingerprint.

Cite this