Erdős--Pósa property of cycles that are far apart
This extends the classical Erdős–Pósa theorem to a setting with distance constraints, providing a structural result for graph theory.
The paper proves an Erdős–Pósa type property for cycles that are pairwise far apart (distance > d), showing a trade-off between the number of such cycles and the size of a vertex set whose removal at distance g(d) makes the graph a forest.
We prove that there exist functions $f,g:\mathbb{N}\to\mathbb{N}$ such that for all nonnegative integers $k$ and $d$, for every graph $G$, either $G$ contains $k$ cycles such that vertices of different cycles have distance greater than $d$ in $G$, or there exists a subset $X$ of vertices of $G$ with $|X|\leq f(k)$ such that $G-B_G(X,g(d))$ is a forest, where $B_G(X,r)$ denotes the set of vertices of $G$ having distance at most $r$ from a vertex of $X$.