Long cycles have the edge-Erdős-Pósa property
We prove that the set of long cycles has the edge-Erd\H{o}s-P\'osa property: for every fixed integer $\ell\ge 3$ and every $k\in\mathbb{N}$, every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ (long cycles) or an edge set $X$ of size $O(k^2\log k + \ell k)$ such t...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
2016
|
| In: |
Arxiv
Year: 2016, Pages: 1-29 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1607.01903
|
| Verfasserangaben: | Henning Bruhn, Matthias Heinlein and Felix Joos |
| Zusammenfassung: | We prove that the set of long cycles has the edge-Erd\H{o}s-P\'osa property: for every fixed integer $\ell\ge 3$ and every $k\in\mathbb{N}$, every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ (long cycles) or an edge set $X$ of size $O(k^2\log k + \ell k)$ such that $G-X$ does not contain any long cycle. This answers a question of Birmel\'e, Bondy, and Reed (Combinatorica 27 (2007), 135--145). |
|---|---|
| Beschreibung: | Identifizierung der Ressource nach: 30 May 2017 Gesehen am 27.07.2022 |
| Beschreibung: | Online Resource |