The number of graphs not containing K₃,3 as a minor

zbMATH Open1163.05319arXiv0803.4418MaRDI QIDQ1010848FDOQ1010848

Authors: Stefanie Gerke, Omer Giménez, Marc Noy, Andreas Weißl 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0803.4418

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Excluding a small minor
• Enumeration and limit laws for series-parallel graphs
• scientific article; zbMATH DE number 2192148
• The extremal function for noncomplete minors
• The structure and labelled enumeration of \(K_{3,3}\)-subdivision-free projective-planar graphs

zbMATH Keywords

generating functionsnumber of labelled graphssymptotic estimates

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cited In (4)

• Random graphs from a weighted minor-closed class
• On the probability of planarity of a random graph near the critical point
• Growth constants of minor-closed classes of graphs
• Enumeration of labelled 4-regular planar graphs. II: Asymptotics

This page was built for publication: The number of graphs not containing \(K_{3,3}\) as a minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010848)