Forcing a sparse minor

Bruce Reed, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

This paper addresses the following question for a given graph H: What is the minimum number f(H) such that every graph with average degree at least f(H) contains H as a minor? Due to connections with Hadwiger's conjecture, this question has been studied in depth when H is a complete graph. Kostochka and Thomason independently proved that . More generally, Myers and Thomason determined f(H) when H has a super-linear number of edges. We focus on the case when H has a linear number of edges. Our main result, which complements the result of Myers and Thomason, states that if H has t vertices and average degree d at least some absolute constant, then . Furthermore, motivated by the case when H has small average degree, we prove that if H has t vertices and q edges, then f(H) a

Original languageEnglish
Pages (from-to)300-322
Number of pages23
JournalCombinatorics, Probability and Computing
Volume25
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016

Cite this