We show that, for every l, the family \( \mathcal{F}_{l} \) of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk2).
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Birmelé, E., Bondy, J.A. & Reed, B.A. The Erdős–Pósa Property For Long Circuits. Combinatorica 27, 135–145 (2007). https://doi.org/10.1007/s00493-007-0047-0
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00493-007-0047-0