On the extremal function for graph minors

2019/07/31 by Andrew Thomason, Matthew Wales · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Biology #Combinatorics #Computer science #Constant (computer programming) #Degree (music) #Function (biology) #Graph #Graph theory and applications #Humanities #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Minor (academic) #Philosophy #Physics #Upper and lower bounds #math.CO #msc:05C83

paper · pdf · doi:10.1002/jgt.22811

published in Journal of Graph Theory 101(1), 66-78 (Wiley) · Final accepted version

arxiv created 2022/02/14 · arxiv updated 2022/02/15 · openalex publication_date 2022/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Abstract For a graph , let , where means that is a minor of . We show that if has average degree , then where is an explicitly defined constant. This bound matches a corresponding lower bound shown to hold for almost all such by Norin, Reed, Wood and the first author.

Citations

• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphies�tze f�r Graphen
• Hadwiger's Conjecture is True for Almost Every Graph
• Lower bound of the hadwiger number of graphs by their average degree
• The Extremal Function for Complete Minors
• An extremal function for contractions of graphs