On the number of graphs not containing K_3,3 as a minor

2008/03/31 by Stefanie Gerke, Omer Giménez, Gerke, S. +5 · 1 citation
Computer Science · Mathematics · #05C30 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.0803.4418

openalex publication_date 2008/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive precise asymptotic estimates for the number of labelled graphs not containing K_3,3 as a minor, and also for those which are edge maximal. Additionally, we establish limit laws for parameters in random K_3,3-minor-free graphs, like the expected number of edges. To establish these results, we translate a decomposition for the corresponding graph class into equations for generating functions and use singularity analysis. We also find a precise estimate for the number of graphs not containing the graph K_3,3 plus an edge as a minor.

Cited by

• Lower Bounds for Induced-Universal Graphs

Related

• On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K4
• Minors in random regular graphs
• Forbidden minors: Finding the finite few
• Graphs without large K_2,n-minors
• The extremal function for K₉^= minors