Journal article
Cycle packing
- Abstract:
-
In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on n vertices can be partitioned into O(n) cycles and edges. They observed that one can easily get an O(n log n)upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(n log log n) cycles and edges suffice. We also prove the Erdős-Gallai conjecture for random graphs and for graphs with linear minimum degree.
- Publication status:
- Published
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 312.1KB, Terms of use)
-
- Publisher copy:
- 10.1002/rsa.20574
Authors
- Publisher:
- Wiley
- Journal:
- Random Structures and Algorithms More from this journal
- Volume:
- 45
- Issue:
- 4
- Pages:
- 608-626
- Publication date:
- 2014-10-16
- Acceptance date:
- 2014-05-13
- DOI:
- EISSN:
-
1098-2418
- ISSN:
-
1042-9832
- Keywords:
- Pubs id:
-
pubs:492183
- UUID:
-
uuid:18e4e91d-e5eb-4a1f-a656-b6eb8d4b47f9
- Local pid:
-
pubs:492183
- Source identifiers:
-
492183
- Deposit date:
-
2016-11-24
- ARK identifier:
Terms of use
- Copyright holder:
- Wiley
- Copyright date:
- 2014
- Notes:
-
This is the author accepted manuscript following peer review version of the article. The final version is
available online from Wiley at: https://doi.org/10.1002/rsa.20574
If you are the owner of this record, you can report an update to it here: Report update to this record