A Tighter Erdős‐Pósa Function for Long Cycles |
| |
| Authors: | Samuel Fiorini Audrey Herinckx |
| |
| Affiliation: | DEPARTMENT OF MATHEMATICS, UNIVERSITé LIBRE DE BRUXELLES, BOULEVARD DU TRIOMPHE, B‐1050 BRUSSELS, BELGIUM |
| |
| Abstract: | We prove that there exists a bivariate function f with  such that for every natural k and ?, every graph G has at least k vertex‐disjoint cycles of length at least ? or a set of at most  vertices that meets all cycles of length at least ?. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with  . |
| |
| Keywords: | Erdő s‐Pó sa property cycles |
|
|
