Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph

DOI10.1016/j.jctb.2023.10.004arXiv2202.05557MaRDI QIDQ6144408

P. D. Seymour, Alexander D. Scott

Publication date: 29 January 2024

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberinduced subgraphcomplete multipartite graph

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey-type theorems
• Induced subtrees in graphs of large chromatic number
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Applications of hypergraph coloring to coloring graphs not inducing certain trees
• Towards Erdős-Hajnal for graphs with no 5-hole
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Radius two trees specify χ‐bounded classes
• A survey of χ‐boundedness
• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• Polynomial bounds for chromatic number II: Excluding a star‐forest
• Polynomial bounds for chromatic number. III. Excluding a double star
• Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs

This page was built for publication: Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph