pith. sign in

arxiv: 1207.5329 · v1 · pith:W4L3OZJLnew · submitted 2012-07-23 · 🧮 math.CO · cs.DM

Forbidding Kuratowski Graphs as Immersions

classification 🧮 math.CO cs.DM
keywords graphskuratowskirelationtopologicalcharacterizationcontainsgivegraph
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.