Approximate path decompositions of regular graphs

Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1

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 th…