The Erdős–Pósa Property for Long Circuits
Dirk Meierling, Dieter Rautenbach, Thomas Sasse · Journal of Graph Theory · 2013
Abstract For an integer ℓ at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ℓ, then there is a set X of at most vertices that intersects all circuits of length at least ℓ. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erdős–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ℓ vertices always suffice.