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

Author: 

Scott, A
Seymour, P

Publication Date: 

1 February 2020

Journal: 

European Journal of Combinatorics

Last Updated: 

2019-12-03T11:34:32.617+00:00

Volume: 

84

DOI: 

10.1016/j.ejc.2019.103024

page: 

103024-103024

abstract: 

© 2019 Elsevier Ltd 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.

Symplectic id: 

1070389

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article