Volume 92, Issue 3 pp. 237-254
ARTICLE

Induced subgraphs of graphs with large chromatic number. XII. Distant stars

Maria Chudnovsky

Maria Chudnovsky

Princeton University, Princeton, New Jersey

Search for more papers by this author
Alex Scott

Corresponding Author

Alex Scott

Mathematical Institute, University of Oxford, Oxford, UK

Correspondence Alex Scott, Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK. Email: [email protected]

Search for more papers by this author
Paul Seymour

Paul Seymour

Princeton University, Princeton, New Jersey

Search for more papers by this author
First published: 11 February 2019
Citations: 14

Abstract

The Gyárfás-Sumner conjecture asserts that if urn:x-wiley:03649024:media:jgt22450:jgt22450-math-0001 is a tree then every graph with bounded clique number and very large chromatic number contains urn:x-wiley:03649024:media:jgt22450:jgt22450-math-0002 as an induced subgraph. This is still open, although it has been proved for a few simple families of trees, including trees of radius two, some special trees of radius three, and subdivided stars. These trees all have the property that their vertices of degree more than two are clustered quite closely together. In this paper, we prove the conjecture for two families of trees which do not have this restriction. As special cases, these families contain all double-ended brooms and two-legged caterpillars.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.