CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001129

[img] PDF - Submitted Version
See Usage Policy.

226Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001129

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1002/rsa.20574DOIArticle
https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20574PublisherArticle
https://arxiv.org/abs/1310.0632arXivDiscussion Paper
http://rsa2013.amu.edu.pl/Related ItemConference Site
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
David and Lucile Packard FoundationUNSPECIFIED
Simons FoundationUNSPECIFIED
NSFDMS-1069197
Alfred P. Sloan FoundationUNSPECIFIED
MIT NEC CorporationUNSPECIFIED
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:https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001129
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
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:19 Aug 2019 20:50
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page