On the purity of minor-closed classes of graphs
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, gap...
Main Authors: | , |
---|---|
Format: | Journal article |
Published: |
Elsevier
2018
|