Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
Abstract
Let be a tree. It was proved by Rödl that graphs that do not contain as an induced subgraph, and do not contain the complete bipartite graph 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 , the degeneracy is at most polynomial in . This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 07, 2022
- Source ID
- 10.1002/jgt.22880
Entities
People
- Alexander David Scott
- Paul Seymour
- Sophie Spirkl
Organizations
- Air Force Office of Scientific Research
- Engineering and Physical Sciences Research Council
- National Science Foundation
- Natural Sciences and Engineering Research Council
- Princeton University
- University of Oxford
- University of Waterloo