 # Path and cycle decompositions of dense graphs

• Bertille Granet (University of Birmingham)
• Thursday 17 October 2019, 14:00-15:00
• Watson LTB.

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 ⌊n/2⌋ paths, while a conjecture of Hajós states that any Eulerian graph on n vertices can be decomposed into at most ⌈(n-1)/2⌉ 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 n/2+o(n) paths. (ii) If G is Eulerian, then it can be decomposed into n/2+o(n) cycles. (iii) G can be decomposed into 3n/2+o(n) cycles and edges. All bounds in (i)-(iii) are asymptotically best possible.

This is joint work with António Girão, Daniela Kühn, and Deryk Osthus.

This talk is part of the Combinatorics and Probability Seminar series.