Toroidal Obstructions with No K_5 Minor

Finding the complete set of forbidden minors for the torus remains an open problem. We determine the complete list of toroidal minor obstructions with no $K_5$ minor and prove that there are exactly $74$, each with between $10$ and $14$ vertices. Combined with the known classification of toroidal obstructions with no $K_{3,3}$ minor, this determines every toroidal obstruction that excludes one of the forbidden minors for planarity. The proof uses three-vertex cuts to show that, apart from $K_{3,7}$, every three-connected obstruction in this class has two distinct independent triples, each the common neighborhood of at least two degree-three vertices. The classification proceeds by considering the possible intersections of these triples and reduces each case by planarity tests and enumeration of the possible graph forms. From the $74$ minor obstructions we also obtain a complete list of $381$ topological obstructions for the torus with no $K_5$ minor.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22089
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Toroidal Obstructions with No K_5 Minor

Austin Ulrigg
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Toroidal Obstructions with No K_5 Minor

Austin Ulrigg
preprint en

Abstract

Finding the complete set of forbidden minors for the torus remains an open problem. We determine the complete list of toroidal minor obstructions with no $K_5$ minor and prove that there are exactly $74$, each with between $10$ and $14$ vertices. Combined with the known classification of toroidal obstructions with no $K_{3,3}$ minor, this determines every toroidal obstruction that excludes one of the forbidden minors for planarity. The proof uses three-vertex cuts to show that, apart from $K_{3,7}$, every three-connected obstruction in this class has two distinct independent triples, each the common neighborhood of at least two degree-three vertices. The classification proceeds by considering the possible intersections of these triples and reduces each case by planarity tests and enumeration of the possible graph forms. From the $74$ minor obstructions we also obtain a complete list of $381$ topological obstructions for the torus with no $K_5$ minor.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon