A Caltech Library Service

Cycle packing

Conlon, David and Fox, Jacob and Sudakov, Benny (2014) Cycle packing. Random Structures & Algorithms, 45 (4). pp. 608-626. ISSN 1042-9832. doi:10.1002/rsa.20574.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Site
Conlon, David0000-0001-5899-1829
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.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Simons FoundationUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021-149111
Binational Science Foundation (USA-Israel)UNSPECIFIED
Subject Keywords:Graph decompositions; cycles; expanders; Erdős‐Gallai conjecture
Issue or Number:4
Record Number:CaltechAUTHORS:20190812-163001129
Persistent URL:
Official Citation:Conlon, D. , Fox, J. and Sudakov, B. (2014), Cycle packing. Random Struct. Alg., 45: 608-626. doi:10.1002/rsa.20574
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97846
Deposited By: Melissa Ray
Deposited On:19 Aug 2019 20:50
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page