Tight Bounds for Cycle-Edge Decompositions and Covers

Saieed Akbari, Jonny Aloni, Arash Beikmohammadi +1

An old conjecture of Erd{ő}s and Gallai states that every $n$ vertex graph can be decomposed, that is $E(G)$ can be partitioned, into $O(n)$ cycles and edges. The covering version…