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 f(Kt) = ct √ lnt. 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 f(H) 6 3.895 √ lndt. 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) 6 t + 6.291q (where the coefficient of 1 in thet term is best possible). 2010 Mathematics Subject Classification. 05C83, 05C35, 05D40.
['Bruce A. Reed', 'David R. Wood']
Forcing a sparse minor