Induced subgraphs of graphs with large chromatic number. XII. Distant stars
From MaRDI portal
Publication:5207465
DOI10.1002/JGT.22450zbMATH Open1429.05063arXiv1711.08612OpenAlexW2962935610WikidataQ128422010 ScholiaQ128422010MaRDI QIDQ5207465FDOQ5207465
Maria Chudnovsky, Paul Seymour, Alex Scott
Publication date: 30 December 2019
Published in: Journal of Graph Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1711.08612
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 (11)
- Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs
- Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture
- Polynomial bounds for chromatic number II: Excluding a star‐forest
- Polynomial bounds for chromatic number. III. Excluding a double star
- Graphs of large chromatic number
- A note on a conjecture of Gy\'arf\'as
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
- A note on the Gyárfás-Sumner conjecture
- Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
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)
