Packing and Covering Immersions in 4-Edge-Connected Graphs

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. In this paper, we prove an edge-variant of the Erdős-Pósa property with respect to the immersion containment in 4-edge-connected graphs. More precisely, we prove that for every graph $H$, there exists a function $f$ such that for every 4-edge-connected graph $G$, either $G$ contains $k$ pairwise edge-disjoint subgraphs each containing $H$ as an immersion, or there exists a set of at most $f(k)$ edges of $G$ intersecting all such subgraphs. This theorem is best possible in the sense that the 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

References in corpus (4)

• Tangle-tree duality in abstract separation systems
• Tangle-tree duality: in graphs, matroids and beyond
• Packing Topological Minors Half-Integrally
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three

Cited by in corpus (3)

• Packing Topological Minors Half-Integrally
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Packing and Covering Immersion Models of Planar subcubic Graphs