Long cycles have the edge-Erdős-Pósa property

Abstract

We prove that the set of long cycles has the edge-Erdős-Pósa property: for every fixed integer $\ell \ge 3$ and every $k\in \mathbb{N}$, every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ (long cycles) or an edge set $X$ of size $O(k^2\log k+\ell k)$ such that $G-X$ does not contain any long cycle. This answers a question of Birmelé, Bondy, and Reed (Combinatorica 27 (2007), 135--145).

29 pages, 6 figures