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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

The Gyárfás-Sumner conjecture asserts that if (Formula presented.) is a tree then every graph with bounded clique number and very large chromatic number contains (Formula presented.) 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.

Original languageEnglish (US)
Pages (from-to)237-254
Number of pages18
JournalJournal of Graph Theory
Volume92
Issue number3
DOIs
StatePublished - Nov 1 2019

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • colouring
  • χ-bounded

Fingerprint

Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. XII. Distant stars'. Together they form a unique fingerprint.

Cite this