Chromatic number and subtrees of graphs
type: Item
instance of: scholarly article
title: Chromatic number and subtrees of graphs
zbMATH Open document ID: 1421.05046
author: Yingli Zhang
author: Baogang Xu
published in: Frontiers of Mathematics in China
publication date: 2018-01-10T00:00:00Z
review text: A. Gyárfás and D. Sumner independently conjectured that for every tree \(T\) the family of graphs not inducing \(T\) as a subgraph is \(\omega\)-bounded, where \(\omega\) denotes the chromatic number. There have been many papers on this still unsolved conjecture. The authors prove that trees obtained by identifying one end of a path with the central vertex of a star are \(\omega\)-bounded. They also improve the bound on a topological version of the conjecture.
reviewed by: Brian Alspach
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 6823739
zbMATH Keywords: chromatic number
zbMATH Keywords: clique number
zbMATH Keywords: induced tree
zbMATH Keywords: subdivision
zbMATH Keywords: Gyárfás-Sumner Conjecture
MaRDI profile type: Publication
full work available at URL: s11464-016-0613-0
OpenAlex ID: W2558609655
cites work: Q5422499
cites work: Substitution and \(\chi\)-boundedness
cites work: The strong perfect graph theorem
cites work: Graph Theory and Probability
cites work: Q4063176
cites work: Q5749319
cites work: Induced subtrees in graphs of large chromatic number
cites work: Radius two trees specify χ‐bounded classes
cites work: Radius Three Trees in Graphs with Large Chromatic Number
cites work: Sur le coloriage des graphs
cites work: Q3129824
cites work: Q3932997
cites work: Q5550921
DOI: 10.1007/S11464-016-0613-0
description: scientific article; zbMATH DE number 6823739