Far-apart Erdős--Pósa property of long cycles

Abstract

We prove that there exist functions $f:{\mathbb{N}}^2\to \mathbb{N}$ and $g:\mathbb{N}\to \mathbb{N}$ such that for all positive integers $k$, $d$, and $\ell \ge 3$, every graph $G$ either contains $k$ cycles of length at least $\ell$ that are pairwise at distance greater than $d$, or admits a subset of vertices $X$ with $|X|\le f(k,\ell )$ such that $G-B_G(X,g(d))$ contains no cycle of length at least $\ell$, where $B_G(X,r)$ denotes the ball of radius $r$ around $X$. This generalizes a theorem of Dujmović, Joret, Micek, and Morin (2024), which established the $\ell =3$ case. Moreover, we prove that the theorem holds with $f(k,\ell )\in \mathcal{O}(\ell k\log k)$ and $g(d)\in \mathcal{O}(d)$. The linear bound on $g$ is best possible, while the bound on $f$ is optimal as a function of $k$ for every fixed $\ell$. In particular, for $\ell =3$ our result improves the previous bound of $\mathcal{O}(k^{18}\mathsf{polylog}k)$ by Dujmović et al.

Topics & keywords