Approximate path decompositions of regular graphs
Abstract We show that the edges of any ‐regular graph can be almost decomposed into paths of length roughly , giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a ‐regular graph can be partitioned into paths, asymptotically confirming a conjecture of Magnant and Martin from 2009.
Authors
- Alp Müyesser (ORCID: https://orcid.org/0009-0006-3702-9749)
- Richard Montgomery (ORCID: https://orcid.org/0000-0001-5293-6837)
- Benny Sudakov (ORCID: https://orcid.org/0000-0003-3307-9475)
- Alexey Pokrovskiy (ORCID: https://orcid.org/0000-0002-8989-3962)
Institutions
- ETH Zurich (CH)
- University of Warwick (GB)
- University of Oxford (GB)
- University College London (GB)
Publication Details
- Journal
- Journal of the London Mathematical Society
- Published
- 2025-08-01
- DOI
- https://doi.org/10.1112/jlms.70269
- Citations
- 1
- Primary Topic
- graph theory and CDMA systems
- Type
- article
- Field-Weighted Citation Impact
- 0.73
Funders
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- European Research Council