Polynomial bounds for chromatic number VI. Adding a four-vertex path

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.ejc.2023.103710

Polynomial bounds for chromatic number VI. Adding a four-vertex path

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

A hereditary class of graphs is χ-bounded if there is a function f such that every graph G in the class has chromatic number at most f(ω(G)), where ω(G) is the clique number of G; and the class is polynomially χ-bounded if f can be taken to be a polynomial. The Gyárfás–Sumner conjecture asserts that, for every forest H, the class of H-free graphs (graphs with no induced copy of H) is χ-bounded. Let us say a forest H is good if it satisfies the stronger property that the class of H-free graphs is polynomially χ-bounded. Very few forests are known to be good: for example, the goodness of the five-vertex path is open. Indeed, it is not even known that if every component of a forest H is good then H is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter (with corresponding polynomial ω(G)¹⁶); and more generally, that if H is good then so is the disjoint union of H and a four-vertex path. We also prove an even more general result: if every component of H₁ is good, and H₂ is any path (or broom) then the class of graphs that are both H₁-free and H₂-free is polynomially χ-bounded.

Original language	American English
Article number	103710
Journal	European Journal of Combinatorics
Volume	110
DOIs	https://doi.org/10.1016/j.ejc.2023.103710
State	Published - May 2023

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2023.103710

Cite this

@article{42009790cf73413fbc75d8e91f0a118e,

title = "Polynomial bounds for chromatic number VI. Adding a four-vertex path",

abstract = "A hereditary class of graphs is χ-bounded if there is a function f such that every graph G in the class has chromatic number at most f(ω(G)), where ω(G) is the clique number of G; and the class is polynomially χ-bounded if f can be taken to be a polynomial. The Gy{\'a}rf{\'a}s–Sumner conjecture asserts that, for every forest H, the class of H-free graphs (graphs with no induced copy of H) is χ-bounded. Let us say a forest H is good if it satisfies the stronger property that the class of H-free graphs is polynomially χ-bounded. Very few forests are known to be good: for example, the goodness of the five-vertex path is open. Indeed, it is not even known that if every component of a forest H is good then H is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter (with corresponding polynomial ω(G)16); and more generally, that if H is good then so is the disjoint union of H and a four-vertex path. We also prove an even more general result: if every component of H1 is good, and H2 is any path (or broom) then the class of graphs that are both H1-free and H2-free is polynomially χ-bounded.",

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

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Ltd",

year = "2023",

month = may,

doi = "10.1016/j.ejc.2023.103710",

language = "American English",

volume = "110",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Polynomial bounds for chromatic number VI. Adding a four-vertex path

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2023/5

Y1 - 2023/5

N2 - A hereditary class of graphs is χ-bounded if there is a function f such that every graph G in the class has chromatic number at most f(ω(G)), where ω(G) is the clique number of G; and the class is polynomially χ-bounded if f can be taken to be a polynomial. The Gyárfás–Sumner conjecture asserts that, for every forest H, the class of H-free graphs (graphs with no induced copy of H) is χ-bounded. Let us say a forest H is good if it satisfies the stronger property that the class of H-free graphs is polynomially χ-bounded. Very few forests are known to be good: for example, the goodness of the five-vertex path is open. Indeed, it is not even known that if every component of a forest H is good then H is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter (with corresponding polynomial ω(G)16); and more generally, that if H is good then so is the disjoint union of H and a four-vertex path. We also prove an even more general result: if every component of H1 is good, and H2 is any path (or broom) then the class of graphs that are both H1-free and H2-free is polynomially χ-bounded.

AB - A hereditary class of graphs is χ-bounded if there is a function f such that every graph G in the class has chromatic number at most f(ω(G)), where ω(G) is the clique number of G; and the class is polynomially χ-bounded if f can be taken to be a polynomial. The Gyárfás–Sumner conjecture asserts that, for every forest H, the class of H-free graphs (graphs with no induced copy of H) is χ-bounded. Let us say a forest H is good if it satisfies the stronger property that the class of H-free graphs is polynomially χ-bounded. Very few forests are known to be good: for example, the goodness of the five-vertex path is open. Indeed, it is not even known that if every component of a forest H is good then H is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter (with corresponding polynomial ω(G)16); and more generally, that if H is good then so is the disjoint union of H and a four-vertex path. We also prove an even more general result: if every component of H1 is good, and H2 is any path (or broom) then the class of graphs that are both H1-free and H2-free is polynomially χ-bounded.

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

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

U2 - 10.1016/j.ejc.2023.103710

DO - 10.1016/j.ejc.2023.103710

M3 - Article

SN - 0195-6698

VL - 110

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103710

ER -

Polynomial bounds for chromatic number VI. Adding a four-vertex path

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this