2018/10/30 by Matt DeVos, DeVos, Matt, Mahdieh Malekian +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1810.12873
24 pages, 15 figures. arXiv admin note: text overlap with arXiv:1810.12863
openalex publication_date 2018/10/30 · arxiv created 2018/11/02 · arxiv updated 2018/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Kuratowski-Wagner Theorem asserts that a graph is planar if and only if it does not have either K3,3 or K5 as a minor. Using this Wagner obtained a precise description of all graphs with no K3,3 minor and all graphs with no K5 minor. Similar results have been achieved for the class of graphs with no H-minor for a number of small graphs H. In this paper we give a precise structure theorem for graphs which do not contain K3,3 as an immersion. This strengthens an earlier theorem of Giannopoulou, Kamiński, and Thilikos that gives a rough description of the class of graphs with no K3,3 or K5 immersion.