2015/04/30 by Kurauskas, Valentas
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.08107
Let \rm 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,…,n\. We present new results in the case when \rm 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 = \K4\. For any fixed k = 1, 2, … we derive precise asymptotic counting formulas and describe the structure of typical graphs that have at most k disjoint minors K4. For k = 0 this is the well-known class of series-parallel graphs. For k ≥ 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.