Complete minors and average degree: A short proof

DOI10.1002/JGT.22937MaRDI QIDQ6074598zbMATH OpenFDO

Authors Noga Alon, Michael Krivelevich, Benny Sudakov

Publication date 12 October 2023

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

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

zbMATH Keywords

probabilistic methodsclique minors

Mathematics Subject Classification ID

Graph minors (05C83) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree $d$ has a complete minor of order $d/sqrtlogd$.

Recommendations

• A lower bound on the average degree forcing a minor
• Small minors in dense graphs
• Logarithmically small minors and topological minors
• Forcing unbalanced complete bipartite minors
• On \(K_{s,t}\)-minors in graphs with given average degree

Cites work

• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• An extremal function for contractions of graphs
• Homomorphiesätze für Graphen
• Lower bound of the Hadwiger number of graphs by their average degree
• The extremal function for complete minors

Cited in

(5)

• Average degree conditions forcing a minor
• Small minors in dense graphs
• Logarithmically small minors and topological minors
• Large complete minors in random subgraphs
• A lower bound on the average degree forcing a minor

This page was built for publication: Complete minors and average degree: A short proof

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