Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Alex Scott; Paul Seymour

doi:10.1016/j.ejc.2019.103024

Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Alex Scott, Paul Seymour

Mathematics

Princeton University

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

2 Scopus citations

Abstract

Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is χ-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees T, but has been proved for some particular trees. For k≥1, let us say a broom of length k is a tree obtained from a k-edge path with ends a,b by adding some number of leaves adjacent to b, and we call a its handle. A tree obtained from brooms of lengths k₁,…,k_n by identifying their handles is a (k₁,…,k_n)-multibroom. Kierstead and Penrice (1994) proved that every (1,…,1)-multibroom T satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,…,2)-multibrooms. In this paper we give a common generalization; we prove that every (1,…,1,2,…,2)-multibroom satisfies the Gyárfás-Sumner conjecture.

Original language	American English
Article number	103024
Journal	European Journal of Combinatorics
Volume	84
DOIs	https://doi.org/10.1016/j.ejc.2019.103024
State	Published - Feb 2020

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2019.103024

Cite this

@article{ec14aad254d64016a86296a7d581410d,

title = "Induced subgraphs of graphs with large chromatic number. XIII. New brooms",

abstract = "Gy{\'a}rf{\'a}s (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is χ-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees T, but has been proved for some particular trees. For k≥1, let us say a broom of length k is a tree obtained from a k-edge path with ends a,b by adding some number of leaves adjacent to b, and we call a its handle. A tree obtained from brooms of lengths k1,…,kn by identifying their handles is a (k1,…,kn)-multibroom. Kierstead and Penrice (1994) proved that every (1,…,1)-multibroom T satisfies the Gy{\'a}rf{\'a}s–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,…,2)-multibrooms. In this paper we give a common generalization; we prove that every (1,…,1,2,…,2)-multibroom satisfies the Gy{\'a}rf{\'a}s-Sumner conjecture.",

author = "Alex Scott and Paul Seymour",

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

year = "2020",

month = feb,

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

language = "American English",

volume = "84",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Induced subgraphs of graphs with large chromatic number. XIII. New brooms

AU - Scott, Alex

AU - Seymour, Paul

PY - 2020/2

Y1 - 2020/2

N2 - Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is χ-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees T, but has been proved for some particular trees. For k≥1, let us say a broom of length k is a tree obtained from a k-edge path with ends a,b by adding some number of leaves adjacent to b, and we call a its handle. A tree obtained from brooms of lengths k1,…,kn by identifying their handles is a (k1,…,kn)-multibroom. Kierstead and Penrice (1994) proved that every (1,…,1)-multibroom T satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,…,2)-multibrooms. In this paper we give a common generalization; we prove that every (1,…,1,2,…,2)-multibroom satisfies the Gyárfás-Sumner conjecture.

AB - Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is χ-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees T, but has been proved for some particular trees. For k≥1, let us say a broom of length k is a tree obtained from a k-edge path with ends a,b by adding some number of leaves adjacent to b, and we call a its handle. A tree obtained from brooms of lengths k1,…,kn by identifying their handles is a (k1,…,kn)-multibroom. Kierstead and Penrice (1994) proved that every (1,…,1)-multibroom T satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,…,2)-multibrooms. In this paper we give a common generalization; we prove that every (1,…,1,2,…,2)-multibroom satisfies the Gyárfás-Sumner conjecture.

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

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

U2 - 10.1016/j.ejc.2019.103024

DO - 10.1016/j.ejc.2019.103024

M3 - Article

SN - 0195-6698

VL - 84

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103024

ER -

Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this