Immersions in Highly Edge Connected Graphs
Dániel Marx, Paul Wollan · SIAM Journal on Discrete Mathematics · 2014
We consider the problem of how much edge connectivity is necessary to force a graph $G$ to contain a fixed graph $H$ as an immersion. We show that if the maximum degree in $H$ is $\Delta$, then all the examples of $\Delta$-edge connected graphs which do not contain $H$ as a weak immersion must have a treelike decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique $K_t$ as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain $K_t$ as a strong immersion.