The Erdős-Pósa property for long circuits (Q2460617)

Let \(G\) be a graph and \({\mathcal F}\) a family of graphs. A transversal of \({\mathcal F}\) is a set \(X\) of vertices of \(G\) such that \(G-X\) contains no member of \({\mathcal F}\). The family \({\mathcal F}\) is said to have the Erdős-Pósa property if there exists a function \(f:\mathbb N\to\mathbb N\) such that every graph \(G\) contains either \(k\) vertex-disjoint members of \({\mathcal F}\) or a transversal of \({\mathcal F}\) of size at most \(f(k)\). This concept originated in \textit{P. Erdős} and \textit{L. Pósa} [Canad. J. Math. 17, 347--352 (1965; Zbl 0129.39904)], where Erdős and Pósa established the existence of such a function \(f\) when \({\mathcal F}\) is the family of circuits. In this paper, 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)\). This sharpens a result of \textit{C. Thomassen} [J. Graph Theory 12, 101--111 (1988; Zbl 0662.05032)], who obtained a doubly exponential bound on \(f(k)\). Applying a result of \textit{E. Birmelé} [J. Graph Theory 43, No. 1, 24--25 (2003; Zbl 1017.05036)], we obtain as a corollary that graphs without \(k\) vertex-disjoint circuits of length \(l\) or more have tree-width \(O(lk^2)\).