pith. sign in

arxiv: 1205.0940 · v1 · pith:46IQBQBUnew · submitted 2012-05-04 · 🧮 math.CO · cs.DM

A tighter Erd\"os-P\'osa function for long cycles

classification 🧮 math.CO cs.DM
keywords cyclesleasteveryfunctionlengthresultbirmelbivariate
0
0 comments X
read the original abstract

We prove that there exists a bivariate function f with f(k,l) = O(l k log k) such that for every naturals k and l, every graph G has at least k vertex-disjoint cycles of length at least l or a set of at most f(k,l) vertices that meets all cycles of length at least l. This improves a result by Birmel\'e, Bondy and Reed (Combinatorica, 2007), who proved the same result with f(k,l) = \Theta(l k^2).

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.