arXiv Analytics

Sign in

arXiv:2202.08530 [math.CO]AbstractReferencesReviewsResources

Complete minors and average degree -- a short proof

Noga Alon, Michael Krivelevich, Benny Sudakov

Published 2022-02-17Version 1

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/\sqrt{\log d}$.

Comments: 2 pages
Categories: math.CO
Subjects: 05C83, 05C35
Related articles: Most relevant | Search more
arXiv:2307.01184 [math.CO] (Published 2023-07-03)
Finding dense minors using average degree
arXiv:2207.04599 [math.CO] (Published 2022-07-11)
A lower bound of the energy of non-singular graphs in terms of average degree
arXiv:0907.2421 [math.CO] (Published 2009-07-14, updated 2010-09-15)
Complete Minors, Independent Sets, and Chordal Graphs

Links

Toolbox