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

DOI10.1002/JGT.22880MaRDI QIDQ6046682zbMATH OpenOpenAlexWikidataFDO

Authors Alex Scott, Paul Seymour, Sophie Spirkl

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.07927, http://hdl.handle.net/10012/19177

zbMATH Keywords

induced subgraphsbipartite graphs

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Polynomial bounds for chromatic number. III. Excluding a double star
• A note on induced subtrees and chromatic number of graphs
• scientific article; zbMATH DE number 1002021
• scientific article; zbMATH DE number 6612443

Cites work

• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A survey of \(\chi\)-boundedness
• Applications of hypergraph coloring to coloring graphs not inducing certain trees
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Graph Theory and Probability
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Induced subtrees in graphs of large chromatic number
• Radius Three Trees in Graphs with Large Chromatic Number
• Radius two trees specify χ‐bounded classes

Cited in

(9)

• Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Polynomial bounds for chromatic number. III. Excluding a double star
• Hitting all maximum stable sets in \(P_5\)-free graphs
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Polynomial bounds for chromatic number VII. Disjoint holes
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Induced Turán problem in bipartite graphs
• A note on the Gyárfás-Sumner conjecture

This page was built for publication: Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046682)