Forbidding Kuratowski Graphs as Immersions
Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos · Journal of Graph Theory · 2014
Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K5 and K3, 3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for . We also use this result to give a structural characterization of graphs that exclude K3, 3 as an immersion.