Forcing a sparse minor
2016
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(K_t)=ct\sqrt{\ln t}$
. 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)\leq 3.895\sqrt{\ln d}\,t$
. 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 ) ⩽ t + 6.291 q (where the coefficient of 1 in the t term is best possible).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
26
Citations
NaN
KQI