pith. sign in

arxiv: 1603.07588 · v1 · pith:EJWNCJD3new · submitted 2016-03-24 · 🧮 math.CO

A tight ErdH{o}s-P\'osa function for long cycles

classification 🧮 math.CO
keywords cyclesgraphleastlengthvertex-disjointcontainseithermathcal
0
0 comments X
read the original abstract

A classic result of Erd\H{o}s and P\'osa says that any graph contains either $k$ vertex-disjoint 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 $\mathcal 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 $\mathcal O(kl+k\log k)$. These results improve on the work of Birmel\'e, Bondy and Reed '07 and Fiorini and Herinckx '14 and are optimal up to constant factors.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.