Path and cycle decompositions of dense graphs
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 deco...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
15 May 2021
|
| In: |
Journal of the London Mathematical Society
Year: 2021, Volume: 104, Issue: 3, Pages: 1085-1134 |
| ISSN: | 1469-7750 |
| DOI: | 10.1112/jlms.12455 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1112/jlms.12455 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1112/jlms.12455 
|
| Author Notes: | António Girão, Bertille Granet, Daniela Kühn and Deryk Osthus |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 28.11.2022 |
| Physical Description: | Online Resource |
| ISSN: | 1469-7750 |
| DOI: | 10.1112/jlms.12455 |