# On the purity of minor-closed classes of graphs

McDiarmid, C
Przykucki, M

5 September 2018

## Journal:

Journal of Combinatorial Theory. Series B

## Last Updated:

2020-03-12T22:34:31.663+00:00

## DOI:

10.1016/j.jctb.2018.08.010

## abstract:

© 2018 Elsevier Inc. Given a graph H with at least one edge, let gapH(n) denote the maximum difference between the numbers of edges in two n-vertex edge-maximal graphs with no minor H. We show that for exactly four connected graphs H (with at least two vertices), the class of graphs with no minor H is pure, that is, gapH(n)=0 for all n⩾1; and for each connected graph H (with at least two vertices) we have the dichotomy that either gapH(n)=O(1) or gapH(n)=Θ(n). Further, if H is 2-connected and does not yield a pure class, then there is a constant c>0 such that gapH(n)∼cn. We also give some partial results when H is not connected or when there are two or more excluded minors.

641935

Submitted

Journal Article