Finding dense minors using average degree

MaRDI QIDQ6442448zbMATH OpenFDO

Authors Kevin Hendrey, Serguei Norine, Raphael Steiner, Jérémie Turcotte

Publication date 3 July 2023

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Graph minors (05C83)

Abstract: Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$-vertex minor in graphs of average degree at least $t-1$. We show that if $G$ has average degree at least $t-1$, it contains a minor on $t$ vertices with at least $$ edges. We show that this cannot be improved beyond $$. Finally, for $tleq6$ we exactly determine the number of edges we are guaranteed to find in the densest $t$-vertex minor in graphs of average degree at least $t-1$.

This page was built for publication: Finding dense minors using average degree

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