Gyarfas (1975) and Sumner (1981) independently conjectured that for every tree T, the class of graphs not containing T as an induced subgraph is chi-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(1),..., k(n) by identifying their handles is a (k(1),..., k(n))-multibroom. Kierstead and Penrice (1994) proved that every (1,..., 1)-multibroom T satisfies the Gyarfas-Sumner conjecture, and Kierstead and Zhu (2004) proved the same for (2,..., 2)-multibrooms.
展开▼
