Cycle packing
<p>In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on <i>n</i> vertices can be partitioned into <i>O</i>(<i>n</i>) cycles and edges. They observed that one can easily get an <i>O</i>(<i>n</i> log <i>...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Wiley
2014
|
| _version_ | 1826261178113851392 |
|---|---|
| author | Conlon, D Fox, J Sudakov, B |
| author_facet | Conlon, D Fox, J Sudakov, B |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | <p>In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on <i>n</i> vertices can be partitioned into <i>O</i>(<i>n</i>) cycles and edges. They observed that one can easily get an <i>O</i>(<i>n</i> log <i>n</i>)upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that <i>O</i>(<i>n</i> log log <i>n</i>) cycles and edges suffice. We also prove the Erdős-Gallai conjecture for random graphs and for graphs with linear minimum degree.</p> |
| first_indexed | 2024-03-06T19:17:27Z |
| format | Journal article |
| id | oxford-uuid:18e4e91d-e5eb-4a1f-a656-b6eb8d4b47f9 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:17:27Z |
| publishDate | 2014 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:18e4e91d-e5eb-4a1f-a656-b6eb8d4b47f92022-03-26T10:45:45ZCycle packingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:18e4e91d-e5eb-4a1f-a656-b6eb8d4b47f9Symplectic Elements at OxfordWiley2014Conlon, DFox, JSudakov, B <p>In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on <i>n</i> vertices can be partitioned into <i>O</i>(<i>n</i>) cycles and edges. They observed that one can easily get an <i>O</i>(<i>n</i> log <i>n</i>)upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that <i>O</i>(<i>n</i> log log <i>n</i>) cycles and edges suffice. We also prove the Erdős-Gallai conjecture for random graphs and for graphs with linear minimum degree.</p> |
| spellingShingle | Conlon, D Fox, J Sudakov, B 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 |
| work_keys_str_mv | AT conlond cyclepacking AT foxj cyclepacking AT sudakovb cyclepacking |