Average degree conditions forcing a minor∗

Daniel J. Harvey, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)


Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger’s Conjecture, much research has focused on the average degree required to force a complete graph as a minor. Subsequently, various authors have considered the average degree required to force an arbitrary graph H as a minor. Here, we strengthen (under certain conditions) a recent result by Reed and Wood, giving better bounds on the average degree required to force an H-minor when H is a sparse graph with many high degree vertices. This solves an open problem of Reed and Wood, and also generalises (to within a constant factor) known results when H is an unbalanced complete bipartite graph.

Original languageEnglish
Article numberP1.42
Number of pages8
JournalElectronic Journal of Combinatorics
Issue number1
Publication statusPublished - 4 Mar 2016

Cite this