An edge variant of the ErdH{o}s-P\'osa property
classification
🧮 math.CO
cs.DM
keywords
thetacontainsedgeedgeseverygraphmathrmmodel
read the original 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{\'o}sa property holds for every $r\geq 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^2r^3 \mathrm{polylog}~kr)$ and $f_r(k) = O(k^4r^2 \mathrm{polylog}~kr).$
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.