On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K4

Abstract

Let $\mathrm{ex}\mathcal{B}$ be a minor-closed class of graphs with a set $\mathcal{B}$ of minimal excluded minors. We study (a) the asymptotic number of graphs without $k+1$ disjoint minors in $\mathcal{B}$ 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 $\mathrm{ex}\mathcal{B}$ contains arbitrarily large fans for a general (good enough) set of forbidden minors $\mathcal{B}$. A particular case where our results hold is $\mathcal{B}=\{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 $k\ge 1$ 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.

97 pages, 10 figures

References in corpus (1)

• Asymptotic properties of some minor-closed classes of graphs