A tight Erdýos-Posa function for long cycles
Frank Mousset, Andreas Noever, Nemanja Škorić, Felix Weissenberger · arXiv (Cornell University) · 2016
A classic result of Erdős and Posa says that any graph contains either k vertexdisjoint cycles or can be made acyclic by deleting at most O(k log k) vertices. Here we generalize this result by showing that for all numbers k and l and for every graph G, either G contains k vertex-disjoint cycles of length at least l, or there exists a set X of O(kl+k log k) vertices that meets all cycles of length at least l in G. As a corollary, the tree-width of any graph G that does not contain k vertex-disjoint cycles of length at least l is of order O(kl+k log k). These results improve on the work of Birmele, Bondy and Reed ’07 and Fiorini and Herinckx ’14 and are optimal up to constant factors.