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

Abstract

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\ge 4$, there exists an integer $c$ such that for every positive integer $m$, there are at most $c^m$ unlabelled $d$-edge-connected $H$-immersion free $m$-edge graphs with no isolated vertex, while there are superexponentially many unlabelled $(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.

References in corpus (11)

• Tangle-tree duality in abstract separation systems
• Tangle-tree duality: in graphs, matroids and beyond
• Clustered Graph Coloring and Layered Treewidth
• Clustered Variants of Hajós' Conjecture
• Packing and Covering Immersions in 4-Edge-Connected Graphs
• Packing Topological Minors Half-Integrally
• A stronger structure theorem for excluded topological minors
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Excluding subdivisions of bounded degree graphs
• Immersion and clustered coloring
• Small families under subdivision

Cited by in corpus (2)

• Packing and Covering Immersions in 4-Edge-Connected Graphs
• Immersion and clustered coloring