TY - JOUR

T1 - Forcing a sparse minor

AU - Reed, Bruce

AU - Wood, David R.

PY - 2016/3/1

Y1 - 2016/3/1

N2 - 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

AB - 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

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

U2 - 10.1017/S0963548315000073

DO - 10.1017/S0963548315000073

M3 - Article

AN - SCOPUS:84957432550

VL - 25

SP - 300

EP - 322

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 2

ER -