Approximate path decompositions of regular graphs

2024/06/04 by Montgomery, Richard, Müyesser, Alp, Pokrovskiy, Alexey +1 · 5 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2406.02514

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.

Cited by

• Packing subgraphs in regular graphs
• Packing subdivisions into regular graphs
• Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
• New bounds for linear arboricity and related problems
• Cycle-factors of regular graphs via entropy

Related

• Decomposing 8-regular graphs into paths of length 4
• Path decompositions of oriented graphs
• Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1
• On the path partition number of 6-regular graphs
• On vertex-disjoint paths in regular graphs