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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) Chapter/Article |
| Language: | English |
| Published: |
2016
|
| In: |
Arxiv
Year: 2016, Pages: 1-29 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1607.01903
|
| Author Notes: | Henning Bruhn, Matthias Heinlein and Felix Joos |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1810693950 | ||
| 003 | DE-627 | ||
| 005 | 20220820224235.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 220718s2016 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.48550/arXiv.1607.01903 |2 doi | |
| 035 | |a (DE-627)1810693950 | ||
| 035 | |a (DE-599)KXP1810693950 | ||
| 035 | |a (OCoLC)1341464004 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 29 |2 sdnb | ||
| 100 | 1 | |a Bruhn, Henning |e VerfasserIn |0 (DE-588)1234066300 |0 (DE-627)1758740639 |4 aut | |
| 245 | 1 | 0 | |a Long cycles have the edge-Erdős-Pósa property |c Henning Bruhn, Matthias Heinlein and Felix Joos |
| 264 | 1 | |c 2016 | |
| 300 | |a 29 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Identifizierung der Ressource nach: 30 May 2017 | ||
| 500 | |a Gesehen am 27.07.2022 | ||
| 520 | |a 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). | ||
| 650 | 4 | |a Mathematics - Combinatorics | |
| 700 | 1 | |a Heinlein, Matthias |d 1991- |e VerfasserIn |0 (DE-588)1179261518 |0 (DE-627)1667335448 |0 (DE-576)517643014 |4 aut | |
| 700 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Arxiv |d Ithaca, NY : Cornell University, 1991 |g (2016), Artikel-ID 1607.01903, Seite 1-29 |h Online-Ressource |w (DE-627)509006531 |w (DE-600)2225896-6 |w (DE-576)28130436X |7 nnas |a Long cycles have the edge-Erdős-Pósa property |
| 773 | 1 | 8 | |g year:2016 |g elocationid:1607.01903 |g pages:1-29 |g extent:29 |a Long cycles have the edge-Erdős-Pósa property |
| 856 | 4 | 0 | |u http://arxiv.org/abs/1607.01903 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20220718 | ||
| 993 | |a Article | ||
| 994 | |a 2016 | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |p 3 |y j | ||
| 999 | |a KXP-PPN1810693950 |e 4169399234 | ||
| BIB | |a Y | ||
| JSO | |a {"physDesc":[{"extent":"29 S."}],"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"id":{"eki":["509006531"],"zdb":["2225896-6"]},"origin":[{"publisherPlace":"Ithaca, NY ; [Erscheinungsort nicht ermittelbar]","publisher":"Cornell University ; Arxiv.org","dateIssuedKey":"1991","dateIssuedDisp":"1991-"}],"titleAlt":[{"title":"Arxiv.org"},{"title":"Arxiv.org e-print archive"},{"title":"Arxiv e-print archive"},{"title":"De.arxiv.org"}],"part":{"text":"(2016), Artikel-ID 1607.01903, Seite 1-29","extent":"29","year":"2016","pages":"1-29"},"pubHistory":["1991 -"],"language":["eng"],"recId":"509006531","type":{"media":"Online-Ressource","bibl":"edited-book"},"disp":"Long cycles have the edge-Erdős-Pósa propertyArxiv","note":["Gesehen am 28.05.2024"],"title":[{"title":"Arxiv","title_sort":"Arxiv"}]}],"origin":[{"dateIssuedKey":"2016","dateIssuedDisp":"2016"}],"id":{"doi":["10.48550/arXiv.1607.01903"],"eki":["1810693950"]},"name":{"displayForm":["Henning Bruhn, Matthias Heinlein and Felix Joos"]},"note":["Identifizierung der Ressource nach: 30 May 2017","Gesehen am 27.07.2022"],"type":{"media":"Online-Ressource","bibl":"chapter"},"language":["eng"],"recId":"1810693950","title":[{"title_sort":"Long cycles have the edge-Erdős-Pósa property","title":"Long cycles have the edge-Erdős-Pósa property"}],"person":[{"role":"aut","roleDisplay":"VerfasserIn","display":"Bruhn, Henning","given":"Henning","family":"Bruhn"},{"family":"Heinlein","given":"Matthias","roleDisplay":"VerfasserIn","display":"Heinlein, Matthias","role":"aut"},{"roleDisplay":"VerfasserIn","display":"Joos, Felix","role":"aut","family":"Joos","given":"Felix"}]} | ||
| SRT | |a BRUHNHENNILONGCYCLES2016 | ||