Published December 2014
| Version Submitted
Journal Article
Open
Cycle packing
Creators
-
1.
University of Oxford
-
2.
Massachusetts Institute of Technology
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(nlogn) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(nloglogn) cycles and edges suffice. We also prove the Erdős‐Gallai conjecture for random graphs and for graphs with linear minimum degree.
Additional Information
© 2014 Wiley. Issue online 06 February 2015; version of record online 06 February 2015; manuscript accepted 13 May 2014; manuscript received 02 October 2013. Supported by Royal Society University Research Fellowship (to D.C.); Packard Fellowship (to J.F.); Simons Fellowship (to J.F.); NSF Grant (to J.F.) (DMS‐1069197); Alfred P. Sloan Fellowship (to J.F.); MIT NEC Corporation Award (to J.F.); SNSF Grant (to B.S.) (200021‐149111); USA‐Israel BSF Grant (to B.S.). We would like to thank David Ellis and Daniel Kane for helpful remarks. We would also like to thank the anonymous referees for a number of useful comments.Attached Files
Submitted - 1310.0632.pdf
Files
1310.0632.pdf
Additional details
Identifiers
- Eprint ID
- 97846
- Resolver ID
- CaltechAUTHORS:20190812-163001129
Related works
- Describes
- https://arxiv.org/abs/1310.0632 (URL)
- http://rsa2013.amu.edu.pl/ (URL)
Funding
- Royal Society
- David and Lucile Packard Foundation
- Simons Foundation
- NSF
- DMS-1069197
- Alfred P. Sloan Foundation
- MIT NEC Corporation
- Swiss National Science Foundation (SNSF)
- 200021-149111
- Binational Science Foundation (USA-Israel)
Dates
- Created
-
2019-08-19Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department