Packing and Covering Immersion Models of Planar subcubic Graphs

Abstract

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$, such that if $H$ is a connected planar subcubic graph on $h>0$ edges, $G$ is a graph, and $k$ is a non-negative integer, then either $G$ contains $k$ vertex/edge-disjoint subgraphs, each containing $H$ as an immersion, or $G$ contains a set $F$ of $f(k,h)$ vertices/edges such that $G\setminus F$ does not contain $H$ as an immersion.