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

Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1002/jgt.22829

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

Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-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 language	American English
Pages (from-to)	318-322
Number of pages	5
Journal	Journal of Graph Theory
Volume	101
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22829
State	Published - Oct 2022

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

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

Access to Document

10.1002/jgt.22829

Cite this

@article{f7519888e6734ac090da8c08452c25ea,

title = "Polynomial bounds for chromatic number II: Excluding a star-forest",

abstract = "The Gy{\'a}rf{\'a}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{\'a}rf{\'a}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.",

keywords = "Gy{\'a}rf{\'a}s–Sumner conjecture, chromatic number, colouring, induced subgraph, χ-boundedness",

author = "Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2022 Wiley Periodicals LLC.",

year = "2022",

month = oct,

doi = "10.1002/jgt.22829",

language = "American English",

volume = "101",

pages = "318--322",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Polynomial bounds for chromatic number II

T2 - Excluding a star-forest

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2022/10

Y1 - 2022/10

N2 - 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.

AB - 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.

KW - Gyárfás–Sumner conjecture

KW - chromatic number

KW - colouring

KW - induced subgraph

KW - χ-boundedness

UR - http://www.scopus.com/inward/record.url?scp=85127378653&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85127378653&partnerID=8YFLogxK

U2 - 10.1002/jgt.22829

DO - 10.1002/jgt.22829

M3 - Article

SN - 0364-9024

VL - 101

SP - 318

EP - 322

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

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

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this