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, sh...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Wiley-VCH Verlag GmbH & Co.
2015
|
| Online Access: | http://hdl.handle.net/1721.1/92862 |
| _version_ | 1826196695563632640 |
|---|---|
| author | Conlon, David Fox, Jacob Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Conlon, David Fox, Jacob Sudakov, Benny |
| author_sort | Conlon, David |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:35:14Z |
| format | Article |
| id | mit-1721.1/92862 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:35:14Z |
| publishDate | 2015 |
| publisher | Wiley-VCH Verlag GmbH & Co. |
| record_format | dspace |
| spelling | mit-1721.1/928622022-09-30T21:41:59Z Cycle packing Conlon, David Fox, Jacob Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob 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. Royal Society (Great Britain) (University Research Fellowship) Simons Foundation (Fellowship) National Science Foundation (U.S.) (Grant NSF-DMS-1069197) Alfred P. Sloan Foundation (Fellowship) NEC Corporation (MIT NEC Corp. award) Swiss National Science Foundation (SNSF grant 200021-149111) United States-Israel Binational Science Foundation (grant) 2015-01-14T18:25:44Z 2015-01-14T18:25:44Z 2014-12 2013-10 Article http://purl.org/eprint/type/JournalArticle 10429832 http://hdl.handle.net/1721.1/92862 Conlon, David, Jacob Fox, and Benny Sudakov. “Cycle Packing.” Random Struct. Alg. 45, no. 4 (October 16, 2014): 608–626. en_US http://dx.doi.org/10.1002/rsa.20574 Random Structures & Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley-VCH Verlag GmbH & Co. arXiv |
| spellingShingle | Conlon, David Fox, Jacob Sudakov, Benny Cycle packing |
| title | Cycle packing |
| title_full | Cycle packing |
| title_fullStr | Cycle packing |
| title_full_unstemmed | Cycle packing |
| title_short | Cycle packing |
| title_sort | cycle packing |
| url | http://hdl.handle.net/1721.1/92862 |
| work_keys_str_mv | AT conlondavid cyclepacking AT foxjacob cyclepacking AT sudakovbenny cyclepacking |