Abstract: In the 1960s, ErdH{o}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(n log n) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(n log log n) cycles and edges suffice. We also prove the ErdH{o}s-Gallai conjecture for random graphs and for graphs with linear minimum degree.
Recommendations
Cites work
- An Erdős-Gallai conjecture
- Covering the edges of a connected graph by paths
- Covers of Eulerian graphs
- Gallai's conjecture for disconnected graphs
- Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
- Hamiltonian circuits in random graphs
- scientific article; zbMATH DE number 5174567 (Why is no real title available?)
- On maximal paths and circuits of graphs
- On the coverings of graphs
- Probability Inequalities for Sums of Bounded Random Variables
- Subgraph coverings and edge switchings
- The Representation of a Graph by Set Intersections
Cited in
(16)- Long cycles, heavy cycles and cycle decompositions in digraphs
- Decompositions of triangle-free 5-regular graphs into paths of length five
- Path and cycle decompositions of dense graphs
- Monochromatic cycle partitions of graphs with large minimum degree
- Bicycle Routing for Maximum Suntan
- Spanning Trees with Few Branch Vertices
- Decomposing random graphs into few cycles and edges
- Path decompositions of tournaments
- Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
- Towards the Erdős-Gallai cycle decomposition conjecture
- Towards the Erdős-Gallai cycle decomposition conjecture
- Path decompositions of tournaments
- Path decompositions of Eulerian graphs
- Separating the edges of a graph by cycles and by subdivisions of K₄
- Path odd-covers of graphs
- Path decompositions of oriented graphs
This page was built for publication: Cycle packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5256386)
