Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree

2021/04/16 by Scott, Alex, Seymour, Paul, Spirkl, Sophie · 6 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.07927

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.

Cited by

• On the analogue of Esperet's conjecture: Characterizing hereditary classes
• Towards Esperet's Conjecture: Polynomial χ-Bounds for Structured Graph Classes
• Unavoidable induced subgraphs forced by graphs with many vertices of prescribed properties
• Binary matroids and degree-boundedness for pivot-minors
• C₄-free subgraphs of high degree with geometric applications
• Edge-colouring and orientations: applications to degree- and χ-boundedness

Related

• Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
• Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• Polynomial bounds for chromatic number. III. Excluding a double star
• Separating Tree-chromatic number from Path-chromatic Number