Journal article
Polynomial bounds for chromatic number III: excluding a double star
- Abstract:
- A double star is a tree with two internal vertices. It is known that the Gy\'arf\'as-Sumner conjecture holds for double stars, that is, for every double star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an induced subgraph then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Here we prove that $f$ can be chosen to be a polynomial.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 301.2KB, Terms of use)
-
- Publisher copy:
- 10.1002/jgt.22829
Authors
- Publisher:
- Wiley
- Journal:
- Journal of Graph Theory More from this journal
- Volume:
- 101
- Issue:
- 2
- Pages:
- 318-322
- Publication date:
- 2022-04-04
- Acceptance date:
- 2022-02-14
- DOI:
- EISSN:
-
1097-0118
- ISSN:
-
0364-9024
- Language:
-
English
- Keywords:
- Pubs id:
-
1191526
- Local pid:
-
pubs:1191526
- Deposit date:
-
2022-04-17
- ARK identifier:
Terms of use
- Copyright holder:
- Wiley
- Copyright date:
- 2022
- Rights statement:
- © 2022 Wiley Periodicals LLC
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Wiley at: https://doi.org/10.1002/jgt.22829
If you are the owner of this record, you can report an update to it here: Report update to this record