A Tighter Erdős‐Pósa Function for Long Cycles. Issue 2 (5th December 2013) - Fiorini, Samuel; Herinckx, Audrey
Abstract We prove that there exists a bivariate function f with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghxt6thgf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(k, ℓ)=O(ℓ·klogk)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghxt6thfx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(k, ℓ)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghxt6thjg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(k, ℓ)=Θ(ℓ·k2)</alternatives>.