On the purity of minor-closed classes of graphs

Author: 

McDiarmid, C
Przykucki, M

Publication Date: 

5 September 2018

Journal: 

Journal of Combinatorial Theory. Series B

Last Updated: 

2019-09-07T00:28:49.967+01: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.

Symplectic id: 

641935

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article