On the critical densities of minor-closed classes

Abstract

Given a minor-closed class $\mathcal{A}$ of graphs, let ${\beta }_{\mathcal{A}}$ denote the supremum over all graphs in $\mathcal{A}$ of the ratio of edges to vertices. We investigate the set $B$ of all such values ${\beta }_{\mathcal{A}}$, taking further the project begun by Eppstein. Amongst other results, we determine the small values in $B$ (those up to 2); we show that $B$ is `asymptotically dense'; and we answer some questions posed by Eppstein.

31 pages, 4 figures. Copyright 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 License. Manuscript has been accepted to the European Journal of Combinatorics