Complete minors and average degree: A short proof

DOI10.1002/JGT.22937zbMATH Open1522.05456arXiv2202.08530MaRDI QIDQ6074598FDOQ6074598

Authors: Noga Alon, Michael Krivelevich, Benny Sudakov 

Publication date: 12 October 2023

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

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$.

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

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

zbMATH Keywords

probabilistic methodsclique minors

Mathematics Subject Classification ID

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

Cites Work

• The extremal function for complete minors
• Homomorphiesätze für Graphen
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• Lower bound of the Hadwiger number of graphs by their average degree

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)