A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three.

A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. There is an obvious necessary degree condition for the immersion containment: if G contains H as an immersion, then for every integer k , the number of vertices of degree at least k in G is at least the number of vertices of degree at least k in H. In this paper, we prove that this obvious necessary condition is "nearly" sufficient for graphs with no edge-cut of order 3: for every graph H , every H -immersion free graph with no edge-cut of order 3 can be obtained by an edge-sum of graphs, where each of the summands is obtained from a graph violating the obvious degree condition by adding a bounded number of edges. The condition for having no edge-cut of order 3 is necessary. A simple application of this theorem shows that for every graph H of maximum degree d ≥ 4 , there exists an integer c such that for every positive integer m , there are at most c m unlabeled d -edge-connected H -immersion free m -edge graphs with no isolated vertex, while there are superexponentially many unlabeled (d − 1) -edge-connected H -immersion free m -edge graphs with no isolated vertex. Our structure theorem will be applied in a forthcoming paper about determining the clustered chromatic number of the class of H -immersion free graphs. [ABSTRACT FROM AUTHOR]