Abstract
A “double star” is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star (Formula presented.), there is a function (Formula presented.) such that if (Formula presented.) does not contain (Formula presented.) as an induced subgraph then (Formula presented.) (where (Formula presented.) are the chromatic number and the clique number of (Formula presented.)). Here we prove that (Formula presented.) can be chosen to be a polynomial.
| Original language | American English |
|---|---|
| Pages (from-to) | 323-340 |
| Number of pages | 18 |
| Journal | Journal of Graph Theory |
| Volume | 101 |
| Issue number | 2 |
| DOIs | |
| State | Published - Oct 2022 |
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- Gyárfás–Sumner conjecture
- chi-boundedness
- induced subgraph