Research output per year
Research output per year
Bruce Reed, David R. Wood
Research output: Contribution to journal › Article › Research › peer-review
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 language | English |
---|---|
Pages (from-to) | 300-322 |
Number of pages | 23 |
Journal | Combinatorics, Probability and Computing |
Volume | 25 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Mar 2016 |
Research output: Contribution to journal › Comment / Debate › Other › peer-review