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
|
| _version_ | 1797093415886782464 |
|---|---|
| author | McDiarmid, C Przykucki, M |
| author_facet | McDiarmid, C Przykucki, M |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T04:00:02Z |
| format | Journal article |
| id | oxford-uuid:c43d6645-1b7a-4380-b4dc-4d677ee34470 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:00:02Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:c43d6645-1b7a-4380-b4dc-4d677ee344702022-03-27T06:22:02ZOn the purity of minor-closed classes of graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c43d6645-1b7a-4380-b4dc-4d677ee34470Symplectic Elements at OxfordElsevier2018McDiarmid, CPrzykucki, MGiven 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. |
| spellingShingle | McDiarmid, C Przykucki, M On the purity of minor-closed classes of graphs |
| title | On the purity of minor-closed classes of graphs |
| title_full | On the purity of minor-closed classes of graphs |
| title_fullStr | On the purity of minor-closed classes of graphs |
| title_full_unstemmed | On the purity of minor-closed classes of graphs |
| title_short | On the purity of minor-closed classes of graphs |
| title_sort | on the purity of minor closed classes of graphs |
| work_keys_str_mv | AT mcdiarmidc onthepurityofminorclosedclassesofgraphs AT przykuckim onthepurityofminorclosedclassesofgraphs |