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

Gyárfás (1975) and Sumner (1981) independently conjectured that for every tree , the class of graphs not containing 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 , but has been proved for some particular trees. For , let us say a broom of length is a tree obtained from a -edge path with ends by adding some number of leaves adjacent to , and we call its handle. A tree obtained from brooms of lengths by identifying their handles is a -multibroom. Kierstead and Penrice (1994) proved that every -multibroom satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu (2004) proved the same for -multibrooms. In this paper we give a common generalization; we prove that every -multibroom satisfies the Gyárfás-Sumner conjecture.