Path and cycle decompositions of dense graphs - Girao, Antonio; Granet, Bertille; Kühn, Daniela; Osthus, Deryk (Journal of the London Mathematical Society, 2021)
We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on n vertices can be decomposed into at most ⌈n2⌉ paths, while a conjecture of Hajós states that any Eulerian graph on n vertices can be decomposed into at most ⌊n−12⌋ cycles. The Erdős-Gallai conjecture states that any graph on n vertices can be decomposed into O(n) cycles and edges. We show that if G is a sufficiently large graph on n vertices with linear minimum degree, then the following hold. (i)G can be decomposed into at most n2+o(n) paths. (ii)If G is Eulerian, then it can be decomposed into at most n2+o(n) cycles. (iii)G can be decomposed into at most 3n2+o(n) cycles and edges. If in addition G satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such G. (iv)G can be decomposed into maxodd(G)2,Δ(G)2+o(n) paths, where odd(G) is the number of odd-degree vertices of G. (v)If G is Eulerian, then it can be decomposed into Δ(G)2+o(n) cycles. All bounds in (i)-(v) are asymptotically best possible.