Chromatic number and subtrees of graphs (Q1692708)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic number and subtrees of graphs |
scientific article |
Statements
Chromatic number and subtrees of graphs (English)
0 references
10 January 2018
0 references
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.
0 references
chromatic number
0 references
clique number
0 references
induced tree
0 references
subdivision
0 references
Gyárfás-Sumner Conjecture
0 references