Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
Alex Scott, Paul Seymour, Sophie Spirkl
Abstract
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.
Topics & Concepts
Degeneracy (biology)CombinatoricsMathematicsBipartite graphComplete bipartite graphChromatic polynomialBounded functionChromatic scaleTree (set theory)Discrete mathematicsInduced subgraphGraphVertex (graph theory)Mathematical analysisBiologyBioinformaticsLimits and Structures in Graph TheoryAdvanced Graph Theory ResearchGraph Labeling and Dimension Problems