Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2014 | Submitted
Journal Article Open

Cycle packing


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 (231.7 kB)
Name Size Download all
231.7 kB Preview Download

Additional details

August 22, 2023
October 18, 2023