Induced subgraphs of graphs with large chromatic number. XII. Distant stars
From MaRDI portal
Publication:5207465
Abstract: The Gyarfas-Sumner conjecture asserts that if H is a tree then every graph with bounded clique number and very large chromatic number contains H 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.
Recommendations
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Polynomial bounds for chromatic number. III. Excluding a double star
- Chromatic number and subtrees of graphs
- Polynomial bounds for chromatic number II: Excluding a star‐forest
- Radius Three Trees in Graphs with Large Chromatic Number
Cited in
(17)- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees
- A note on a conjecture of Gy\'arf\'as
- Extending the Gyárfás-Sumner conjecture
- Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
- Polynomial bounds for chromatic number II: Excluding a star‐forest
- Polynomial bounds for chromatic number. III. Excluding a double star
- A note on the Gyárfás-Sumner conjecture
- Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs
- Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
- Graphs of large chromatic number
- Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture
- A note on -binding functions and linear forests
- The dichromatic number of digraphs without induced subdigraphs
- -boundedness and related problems on graphs without long induced paths: a survey
- Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
This page was built for publication: Induced subgraphs of graphs with large chromatic number. XII. Distant stars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207465)
