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

DOI10.1002/JGT.22880zbMATH Open1522.05140arXiv2104.07927OpenAlexW3184514170WikidataQ114236116 ScholiaQ114236116MaRDI QIDQ6046682FDOQ6046682

Authors: Alex Scott, Paul Seymour, Sophie Spirkl 

Publication date: 6 October 2023

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

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.

Full work available at URL: https://arxiv.org/abs/2104.07927

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

zbMATH Keywords

induced subgraphsbipartite graphs

Mathematics Subject Classification ID

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

Cites Work

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

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)