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>...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Foilsithe / Cruthaithe: |
Wiley
2014
|
| Achoimre: | <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> |
|---|