On the purity of minor-closed classes of graphs

摘要

Given a graph H with at least one edge, let gap(H)(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, gap(H)(n) = 0 for all n = 1; and for each connected graph H (with at least two vertices) we have the dichotomy that either gap(H) (n) = O(1) or gape(H)(n) = Theta(n). Further, if H is 2-connected and does not yield a pure class, then there is a constant c 0 such that gap(H)(n) similar to cn. We also give some partial results when H is not connected or when there are two or more excluded minors. (C) 2018 Elsevier Inc. All rights reserved.