A classic result of Erdős and Posa states that any graph either contains k   vertex-disjoint cycles or can be made acyclic by deleting at most O(klog⁡k)O(klog⁡k) vertices. Birmele, Bondy, and Reed (2007) raised the following more general question: given numbers l and k  , what is the optimal function f(l,k)f(l,k) such that every graph G either contains k vertex-disjoint cycles of length at least l or contains a set X   of f(l,k)f(l,k) vertices that meets all cycles of length at least l  ? In this paper, we answer that question by proving that f(l,k)=Θ(kl+klog⁡k)f(l,k)=Θ(kl+klog⁡k).#R##N##R##N#As a corollary, the tree-width of any graph G that does not contain k vertex-disjoint cycles of length at least l   is of order O(kl+klog⁡k)O(kl+klog⁡k). This is also optimal up to constant factors and answers another question of Birmele, Bondy, and Reed (2007).
['Frank Mousset', 'Andreas Noever', 'Nemanja Škorić', 'Felix Weissenberger']
A tight Erdős-Pósa function for long cycles