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. https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001129
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 231kB |
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: |
| ||||||||||||||||||
| ORCID: |
| ||||||||||||||||||
| 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: |
| ||||||||||||||||||
| Subject Keywords: | Graph decompositions; cycles; expanders; Erdős‐Gallai conjecture | ||||||||||||||||||
| Issue or Number: | 4 | ||||||||||||||||||
| DOI: | 10.1002/rsa.20574 | ||||||||||||||||||
| 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: | 16 Nov 2021 17:34 |
Repository Staff Only: item control page
