Skip to main content

Graph immersions

Resource type
Thesis type
(Thesis) Ph.D.
Date created
One of the first prominent theorems in structural graph theory is the Kuratowski-Wagner theorem which characterizes planar graphs as those with no K_{3,3} or K_5 minor. Numerous other classical theorems give precise descriptions of the class of graphs with no H-minor for numerous small graphs H. In particular, such classifications exist when H is W_4, W_5, Prism, K_{3,3}, K_5, Octahedron, and Cube. One of the most useful tools in establishing such results are splitter theorems which reduce a graph while preserving both connectivity and containment of a given minor. In this thesis we consider analogous problems for a different containment relation: immersion. Although immersion is a standard containment relation, prior to this thesis there were almost no precise structure theorems for forbidden immersions. The most prominent theorems in this direction give a rough description of graphs with no W_4 immersion and those with no K_{3,3} or K_5 immersion. Our main contributions include precise structure theorems for the class of graphs with no H-immersion when H is one of K_4, W_4, Prism, and K_{3,3}. To assist in this exploration, we have also established two splitter theorems for graph immersions, one for 2k-edge-connected graphs, and another for 3-edge-connected and internally 4-edge-connected graphs.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: DeVos, Matt
Member of collection
Download file Size
etd19986.pdf 1.75 MB

Views & downloads - as of June 2023

Views: 30
Downloads: 4