# Forbidding Kuratowski Graphs as Immersions

5 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph $G$ contains a graph $H$ as a topological minor, then it also contains it as an immersion but not vice versa. Kuratowski graphs, namely $K_{5}$ and $K_{3,3}$, give a precise characterization of planar graphs when excluded as topological minors. In this note we give a structural characterization of the graphs that exclude Kuratowski graphs as immersions. We prove that they can be constructed by applying consecutive $i$-edge-sums, for $i\leq 3$, starting from graphs that are planar sub-cubic or of branch-width at most 10.
Document type :
Journal articles
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904533
Contributor : Dimitrios Thilikos <>
Submitted on : Thursday, November 14, 2013 - 4:14:06 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM

### Citation

Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos. Forbidding Kuratowski Graphs as Immersions. Journal of Graph Theory, Wiley, 2015, 78 (1), pp.43-60. ⟨10.1002/jgt.21790⟩. ⟨lirmm-00904533⟩

Record views