Forcing a sparse minor

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 $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)\le 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)\le t+6.291q$ (where the coefficient of 1 in the $t$ term is best possible).

Cited by in corpus (6)

• Defective colouring of graphs excluding a subgraph or minor
• Extremal density for sparse minors and subdivisions
• Minor-closed graph classes with bounded layered pathwidth
• The extremal function for Petersen minors
• On the extremal function for graph minors
• Phase Transition of Degeneracy in Minor-Closed Families