Random graphs containing few disjoint excluded minors

DOI10.1002/RSA.20447zbMATH Open1303.05178arXiv1504.08107OpenAlexW2073593086MaRDI QIDQ5409864FDOQ5409864

Authors: Valentas Kurauskas, Colin McDiarmid 

Publication date: 15 April 2014

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Let $mex,mathcalB$ be a minor-closed class of graphs with a set $mathcalB$ of minimal excluded minors. We study (a) the asymptotic number of graphs without $k+1$ disjoint minors in $mathcalB$ and (b) the properties of a uniformly random graph drawn from all such graphs on vertices $1,dots,n$. We present new results in the case when $mex,mathcalB$ contains arbitrarily large fans for a general (good enough) set of forbidden minors $mathcalB$. A particular case where our results hold is $mathcalB=K_4$. For any fixed $k=1,2,dots$ we derive precise asymptotic counting formulas and describe the structure of typical graphs that have at most $k$ disjoint minors $K_4$. For $k=0$ this is the well-known class of series-parallel graphs. For $kge1$ we show that typical instances have an elaborate tree-like structure with $2k+1$ special vertices of very high degree. The proofs combine a variety of methods, including new structural results, Robertson and Seymour's graph minor theory and analytic combinatorics.

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

Recommendations

• Random graphs with few disjoint cycles
• Random unlabelled graphs containing few disjoint cycles
• The edge-Erdős-Pósa property
• Excluded Forest Minors and the Erdős–Pósa Property
• The Erdős-Pósa property for clique minors in highly connected graphs

zbMATH Keywords

blockerfandisjoint excluded minors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83)

Cites Work

• Graph minors. XX: Wagner's conjecture
• A partial k-arboretum of graphs with bounded treewidth
• Homomorphiesätze für Graphen
• Graph minors. V. Excluding a planar graph
• Random graphs with few disjoint cycles
• Random graphs from a minor-closed class
• On Independent Circuits Contained in a Graph
• Random planar graphs
• Proper minor-closed families are small
• Random graphs on surfaces
• Random unlabelled graphs containing few disjoint cycles
• On graphs with few disjoint \(t\)-star minors
• Small graph classes and bounded expansion
• Growth constants of minor-closed classes of graphs
• On the presence of disjoint subgraphs of a specified type
• The Erdős-Pósa property for long circuits

Cited In (4)

• Random graphs from a weighted minor-closed class
• On graphs with few disjoint \(t\)-star minors
• Random graphs with few disjoint cycles
• Random unlabelled graphs containing few disjoint cycles

This page was built for publication: Random graphs containing few disjoint excluded minors

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