Montgomery, R;
Müyesser, A;
Pokrovskiy, A;
Sudakov, B;
(2025)
Approximate path decompositions of regular graphs.
Journal of the London Mathematical Society
, 112
(2)
, Article e70269. 10.1112/jlms.70269.
Preview |
Text
Pokrovskiy_Journal of London Math Soc - 2025 - Montgomery - Approximate path decompositions of regular graphs.pdf Download (504kB) | Preview |
Abstract
We show that the edges of any d-regular graph can be almost decomposed into paths of length roughly d, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a d-regular graph can be partitioned into n/(d + 1) paths, asymptotically confirming a conjecture of Magnant and Martin from 2009.
| Type: | Article |
|---|---|
| Title: | Approximate path decompositions of regular graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1112/jlms.70269 |
| Publisher version: | https://doi.org/10.1112/jlms.70269 |
| Language: | English |
| Additional information: | Copyright © 2025 The Author(s). The Journal of the London Mathematical Society is copyright © London Mathematical Society. This is an open access article under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits use, distribution and reproduction in any medium, provided the original work is properly cited. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10213467 |
Archive Staff Only
 |
View Item |
