Towards the Erdős-Gallai Cycle Decomposition Conjecture

Abstract

In the 1960's, Erdős and Gallai conjectured that the edges of any $n$-vertex graph can be decomposed into $O(n)$ cycles and edges. We improve upon the previous best bound of $O(n\log \log n)$ cycles and edges due to Conlon, Fox and Sudakov, by showing an $n$-vertex graph can always be decomposed into $O(n{\log }^{\ast }n)$ cycles and edges, where ${\log }^{\ast }n$ is the iterated logarithm function.

Final version, accepted for publication

Cited by in corpus (1)

• Separating the edges of a graph by a linear number of paths