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 |