On the extremal function for graph minors

Autor: Andrew Thomason, Matthew Wales
Rok vydání: 2022
Předmět:
Zdroj: Journal of Graph Theory. 101:66-78
ISSN: 1097-0118
0364-9024
DOI: 10.1002/jgt.22811
Popis: 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\ldots+o_d(1))|H|\sqrt{\log d} $$ where $0.319\ldots$ 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.
Comment: Final accepted version
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje