University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Path and cycle decompositions of dense graphs

## Path and cycle decompositions of dense graphsAdd to your list(s) Download to your calendar using vCal - Bertille Granet (University of Birmingham)
- Thursday 17 October 2019, 14:00-15:00
- Watson LTB.
If you have a question about this talk, please contact Eoin Long. 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. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsComputer Science Distinguished Seminar IMA West Midlands Branch SoCS PhD Research Training Sessions## Other talksUltrafast, all-optical, and highly efficient imaging of molecular chirality Quantum simulations using ultra cold ytterbium TBC Geometry of alternating projections in metric spaces with bounded curvature Extending the Lax type operator for finite W-algebras Provably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems |