Complete minors and average degree: A short proof

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

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

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

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

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)