New minor minimal non-apex graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908936319270912 |
|---|---|
| author | Pavelescu, Andrei Pavelescu, Elena Potter, Madeline |
| author_facet | Pavelescu, Andrei Pavelescu, Elena Potter, Madeline |
| contents | A graph is apex if it becomes planar after the deletion of one vertex. The family of apex graphs is closed under taking minors, so it is characterized by a finite set of forbidden minors. Determining the finite set of forbidden minors for apex graphs remains an open question. In this paper, we list all forbidden minors for apex graphs with 12 or fewer vertices and all forbidden minors for apex graphs with 26 and fewer edges. We also present graphs outside of these ranges. We show that a graph with 13 vertices and minimal degree 6 is either apex or contains a $K_6$ minor, proving Jørgensen's conjecture for order 13. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03433 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New minor minimal non-apex graphs Pavelescu, Andrei Pavelescu, Elena Potter, Madeline Combinatorics 57M15, 05C10 A graph is apex if it becomes planar after the deletion of one vertex. The family of apex graphs is closed under taking minors, so it is characterized by a finite set of forbidden minors. Determining the finite set of forbidden minors for apex graphs remains an open question. In this paper, we list all forbidden minors for apex graphs with 12 or fewer vertices and all forbidden minors for apex graphs with 26 and fewer edges. We also present graphs outside of these ranges. We show that a graph with 13 vertices and minimal degree 6 is either apex or contains a $K_6$ minor, proving Jørgensen's conjecture for order 13. |
| title | New minor minimal non-apex graphs |
| topic | Combinatorics 57M15, 05C10 |
| url | https://arxiv.org/abs/2604.03433 |