Abstract
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 \geq 1$; and for each connected graph $H$ (with at least two vertices) we have the dichotomy that either $\gap_{H}(n) = O(1)$ or $\gap_{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) \sim cn$. We also give some partial results when $H$ is not connected or when there are two or more excluded minors.
Original language | English |
---|---|
Pages (from-to) | 295-318 |
Number of pages | 24 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 135 |
Early online date | 5 Sept 2018 |
DOIs | |
Publication status | E-pub ahead of print - 5 Sept 2018 |