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 δ, then all the examples of δ-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 Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersion
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 δ, then all the examples of δ-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 Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersion.
Immersions in highly edge connected graphs / Marx, Dániel; Wollan, PAUL JOSEPH. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 28:1(2014), pp. 503-520. [10.1137/130924056]
Immersions in highly edge connected graphs
WOLLAN, PAUL JOSEPH
2014
Abstract
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 δ, then all the examples of δ-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 Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersionI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
