An edge variant of the Erdős-Pósa property

Abstract

For every $r\in \mathbb{N}$, we denote by ${\theta }_r$ the multigraph with two vertices and $r$ parallel edges. Given a graph $G$, we say that a subgraph $H$ of $G$ is a model of ${\theta }_r$ in $G$ if $H$ contains ${\theta }_r$ as a contraction. We prove that the following edge variant of the Erd{\H o}s-P{ó}sa property holds for every $r\ge 2$: if $G$ is a graph and $k$ is a positive integer, then either $G$ contains a packing of $k$ mutually edge-disjoint models of ${\theta }_r$, or it contains a set $S$ of $f_r(k)$ edges such that $G\setminus S$ has no ${\theta }_r$-model, for both $f_r(k)=O(k^2{r}^3\mathrm{polylog}kr)$ and $f_r(k)=O(k^4{r}^2\mathrm{polylog}kr).$

arXiv comment17 pages, 2 figures