An Erdős-Pósa theorem for induced packings of even cycles

Abstract

We show that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k)$ vertices whose closed neighborhood meets every even cycle of $G$. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every $K_{1,t}$-free graph containing no induced packing of $k$ even cycles has tree-independence number $O(t{k}^2\log k)$, with a corresponding decomposition computable in polynomial time.

arXiv comment38 pages, 5 figures