On the growth rate of minor-closed classes of graphs

Abstract

A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class $C$, we let $c_n$ be the number of graphs in $C$ which have $n$ vertices. A recent result of Norine et al. shows that for all minor-closed class $C$, there is a constant $r$ such that $c_n<r^{n}n!$. Our main results show that the growth rate of $c_n$ is far from arbitrary. For example, no minor-closed class $C$ has $c_n=r^{n+o(n)}n!$ with $0<r<1$ or $1<r<\xi \approx 1.76$.

Cited by in corpus (2)

• Overview of some general results in combinatorial enumeration
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs