On the extremal function for graph minors

Abstract

For a graph $H$, let $c(H)=\inf\{c\,:\,e(G)\geq c|G| \mbox{ implies } G\succ H\,\}$, where $G\succ H$ means that $H$ is a minor of $G$. We show that if $H$ has average degree $d$, then $$c(H)\le (0.319\dots +o_d(1))|H|\sqrt{\log d}$$ where $0.319\dots$ is an explicitly defined constant. This bound matches a corresponding lower bound shown to hold for almost all such $H$ by Norin, Reed, Wood and the first author.

arXiv commentFinal accepted version

References in corpus (2)

• Forcing a sparse minor
• A lower bound on the average degree forcing a minor

Cited by in corpus (5)

• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• A lower bound on the average degree forcing a minor
• Extremal functions for sparse minors
• Phase Transition of Degeneracy in Minor-Closed Families
• Densities of minor-closed graph classes are rational