Let (Formula presented.) be a tree. It was proved by Rödl that graphs that do not contain (Formula presented.) as an induced subgraph, and do not contain the complete bipartite graph (Formula presented.) 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 (Formula presented.), the degeneracy is at most polynomial in (Formula presented.). This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- bipartite graphs
- induced subgraphs