Cycle packing
Copyright policy )Cycle packing
AbstractIn 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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 608–626, 2014
- ETH Zurich Switzerland
- Massachusetts Institute of Technology United States
- University of Oxford United Kingdom
- California Institute of Technology United States
cycles, ErdÅ‘sâ€Gallai conjecture, Erdős-Gallai conjecture, 510, 004, graph decompositions, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Erdős‐Gallai conjecture, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Graph decompositions, expanders
cycles, ErdÅ‘sâ€Gallai conjecture, Erdős-Gallai conjecture, 510, 004, graph decompositions, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Erdős‐Gallai conjecture, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Graph decompositions, expanders
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!