Maximum degree in minor-closed classes of graphs

2013/04/18 by Omer Gimenez, Omer Giménez, Dieter Mitsche +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1304.5049

24 pages, 3 figures

arxiv created 2013/04/18 · openalex publication_date 2013/04/18 · arxiv updated 2013/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a class of graphs G closed under taking minors, we study the maximum degree Δ_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Δ_n not observed before, such us log n/ log log log n and log n/ log log log log n.

Related

• The maximum degree of planar graphs I. Series-parallel graphs
• Independent sets in graphs with given minimum degree
• On the growth rate of minor-closed classes of graphs
• Finding forbidden minors in sublinear time: a n^1/2+o(1)-query\n one-sided tester for minor closed properties on bounded degree graphs
• Random graphs from a weighted minor-closed class