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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
15 May 2021
|
| In: |
Journal of the London Mathematical Society
Year: 2021, Jahrgang: 104, Heft: 3, Pages: 1085-1134 |
| ISSN: | 1469-7750 |
| DOI: | 10.1112/jlms.12455 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1112/jlms.12455 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1112/jlms.12455 
|
| Verfasserangaben: | António Girão, Bertille Granet, Daniela Kühn and Deryk Osthus |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1823726186 | ||
| 003 | DE-627 | ||
| 005 | 20230117213241.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221128s2021 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1112/jlms.12455 |2 doi | |
| 035 | |a (DE-627)1823726186 | ||
| 035 | |a (DE-599)KXP1823726186 | ||
| 035 | |a (OCoLC)1360439636 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Girao, Antonio |e VerfasserIn |0 (DE-588)1256755230 |0 (DE-627)1800839561 |4 aut | |
| 245 | 1 | 0 | |a Path and cycle decompositions of dense graphs |c António Girão, Bertille Granet, Daniela Kühn and Deryk Osthus |
| 264 | 1 | |c 15 May 2021 | |
| 300 | |a 50 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 28.11.2022 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 05C38 | |
| 650 | 4 | |a 05C70 | |
| 650 | 4 | |a 05D40 (primary) | |
| 700 | 1 | |a Granet, Bertille |e VerfasserIn |0 (DE-588)1274018277 |0 (DE-627)1823726569 |4 aut | |
| 700 | 1 | |a Kühn, Daniela |d 1973- |e VerfasserIn |0 (DE-588)123412005 |0 (DE-627)082540500 |0 (DE-576)293697906 |4 aut | |
| 700 | 1 | |a Osthus, Deryk |d 1974- |e VerfasserIn |0 (DE-588)12285702X |0 (DE-627)08219744X |0 (DE-576)293449856 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a London Mathematical Society |t Journal of the London Mathematical Society |d Oxford : Wiley, 1926 |g 104(2021), 3, Seite 1085-1134 |h Online-Ressource |w (DE-627)270126953 |w (DE-600)1476428-3 |w (DE-576)078129079 |x 1469-7750 |7 nnas |
| 773 | 1 | 8 | |g volume:104 |g year:2021 |g number:3 |g pages:1085-1134 |g extent:50 |a Path and cycle decompositions of dense graphs |
| 856 | 4 | 0 | |u https://doi.org/10.1112/jlms.12455 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://onlinelibrary.wiley.com/doi/abs/10.1112/jlms.12455 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221128 | ||
| 993 | |a Article | ||
| 994 | |a 2021 | ||
| 998 | |g 1274018277 |a Granet, Bertille |m 1274018277:Granet, Bertille |d 110000 |d 110300 |e 110000PG1274018277 |e 110300PG1274018277 |k 0/110000/ |k 1/110000/110300/ |p 2 | ||
| 999 | |a KXP-PPN1823726186 |e 4220980598 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"person":[{"family":"Girao","given":"Antonio","roleDisplay":"VerfasserIn","display":"Girao, Antonio","role":"aut"},{"role":"aut","display":"Granet, Bertille","roleDisplay":"VerfasserIn","given":"Bertille","family":"Granet"},{"roleDisplay":"VerfasserIn","display":"Kühn, Daniela","role":"aut","family":"Kühn","given":"Daniela"},{"family":"Osthus","given":"Deryk","display":"Osthus, Deryk","roleDisplay":"VerfasserIn","role":"aut"}],"title":[{"title_sort":"Path and cycle decompositions of dense graphs","title":"Path and cycle decompositions of dense graphs"}],"language":["eng"],"recId":"1823726186","type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Gesehen am 28.11.2022"],"name":{"displayForm":["António Girão, Bertille Granet, Daniela Kühn and Deryk Osthus"]},"id":{"eki":["1823726186"],"doi":["10.1112/jlms.12455"]},"origin":[{"dateIssuedKey":"2021","dateIssuedDisp":"15 May 2021"}],"relHost":[{"origin":[{"dateIssuedKey":"1926","publisher":"Wiley ; Cambridge Univ. Press ; Oxford University Press","dateIssuedDisp":"1926-","publisherPlace":"Oxford ; Cambridge ; Oxford"}],"id":{"issn":["1469-7750"],"doi":["10.1112/(ISSN)1469-7750"],"eki":["270126953"],"zdb":["1476428-3"]},"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title":"Journal of the London Mathematical Society","title_sort":"Journal of the London Mathematical Society"}],"pubHistory":["1.1926 -"],"part":{"year":"2021","pages":"1085-1134","issue":"3","volume":"104","text":"104(2021), 3, Seite 1085-1134","extent":"50"},"disp":"London Mathematical SocietyJournal of the London Mathematical Society","note":["Gesehen am 16.08.17"],"type":{"media":"Online-Ressource","bibl":"periodical"},"language":["eng"],"corporate":[{"role":"aut","display":"London Mathematical Society","roleDisplay":"VerfasserIn"}],"recId":"270126953"}],"physDesc":[{"extent":"50 S."}]} | ||
| SRT | |a GIRAOANTONPATHANDCYC1520 | ||