Complete minors and average degree: A short proof

Noga Alon; Michael Krivelevich; Benny Sudakov

doi:10.1002/jgt.22937

Complete minors and average degree: A short proof

Noga Alon, Michael Krivelevich, Benny Sudakov

Mathematics

Research output: Contribution to journal › Article › peer-review

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 (Formula presented.) has a complete minor of order (Formula presented.).

Original language	English (US)
Journal	Journal of Graph Theory
DOIs	https://doi.org/10.1002/jgt.22937
State	Accepted/In press - 2023

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

clique minors
probabilistic methods

Access to Document

10.1002/jgt.22937

Cite this

@article{ac43f3aa236b4dd4a4557746d02773ea,

title = "Complete minors and average degree: A short proof",

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 (Formula presented.) has a complete minor of order (Formula presented.).",

keywords = "clique minors, probabilistic methods",

author = "Noga Alon and Michael Krivelevich and Benny Sudakov",

note = "Funding Information: This research was supported as part by NSF grant DMS‐1855464, USA‐Israel BSF grant 2018267 and by SNSF grant 200021_196965. Publisher Copyright: {\textcopyright} 2023 Wiley Periodicals LLC.",

year = "2023",

doi = "10.1002/jgt.22937",

language = "English (US)",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

}

TY - JOUR

T1 - Complete minors and average degree

T2 - A short proof

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Sudakov, Benny

PY - 2023

Y1 - 2023

N2 - We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree (Formula presented.) has a complete minor of order (Formula presented.).

AB - We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree (Formula presented.) has a complete minor of order (Formula presented.).

KW - clique minors

KW - probabilistic methods

UR - http://www.scopus.com/inward/record.url?scp=85148527700&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85148527700&partnerID=8YFLogxK

U2 - 10.1002/jgt.22937

DO - 10.1002/jgt.22937

M3 - Article

AN - SCOPUS:85148527700

SN - 0364-9024

JO - Journal of Graph Theory

JF - Journal of Graph Theory

ER -

Complete minors and average degree: A short proof

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Cite this