On the growth rate of minor-closed classes of graphs
| dc.creator | Bernardi, Olivier | |
| dc.creator | Noy, Marc | |
| dc.creator | Welsh, Dominic | |
| dc.date | 2007-10-16 | |
| dc.date.accessioned | 2026-07-07T08:36:36Z | |
| dc.date.available | 2026-07-07T08:36:36Z | |
| dc.description | 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 < ξ\approx 1.76$. | |
| dc.identifier | https://arxiv.org/abs/0710.2995 | |
| dc.identifier | http://arxiv.org/abs/0710.2995 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/140117 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C83, 05C30 | |
| dc.title | On the growth rate of minor-closed classes of graphs | |
| dc.type | text |