A Tighter Erdős‐Pósa Function for Long Cycles. Issue 2 (5th December 2013) - Fiorini, Samuel
Abstract We prove that there exists a bivariate function f with f(k, ℓ)=O(ℓ·klogk) such that for every natural k and ℓ, every graph G has at least k vertex‐disjoint cycles of length at least ℓ or a set of at most f(k, ℓ) vertices that meets all cycles of length at least ℓ. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with f(k, ℓ)=Θ(ℓ·k2).