Journal article
Polynomial bounds for chromatic number. I: excluding a biclique and an induced tree
- Abstract:
- Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph $K_{t,t}$ as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree H, the degeneracy is at most polynomial in t. This answers a question of Bonamy, Pilipczuk, Rzazewski, Thomasse and Walczak.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 605.8KB, Terms of use)
-
- Publisher copy:
- 10.1002/jgt.22880
Authors
- Publisher:
- Wiley
- Journal:
- Journal of Graph Theory More from this journal
- Volume:
- 102
- Issue:
- 3
- Pages:
- 458-471
- Publication date:
- 2022-09-07
- Acceptance date:
- 2022-03-23
- DOI:
- EISSN:
-
1097-0118
- ISSN:
-
0364-9024
- Language:
-
English
- Keywords:
- Pubs id:
-
1174104
- Local pid:
-
pubs:1174104
- Deposit date:
-
2022-04-21
- ARK identifier:
Terms of use
- Copyright holder:
- Scott et al
- Copyright date:
- 2022
- Rights statement:
- © 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record