Finding dense minors using average degree
METADATA ONLY
Loading...
Author / Producer
Date
2025-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 (√2 – 1 – o(1)) (ᵗ₂) edges. We show that this cannot be improved beyond (3/4 + o(1)) (ᵗ₂). Finally, for t ≤ 6 we exactly determine the number of edges we are guaranteed to find in the densest
-vertex minor in graphs of average degree at least t – 1.
.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
108 (1)
Pages / Article No.
205 - 223
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
average degree; graph minors; Hadwiger's conjecture