Cycle partitions of regular graphs

Magnant and Martin conjectured that the vertex set of any $d$-regular graph $G$ on $n$ vertices can be partitioned into $n\mathrm{/}(d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d=\mathrm{\Omega }(n)$, improving a result of Han, who showed that in this range almost all vertices of $G$ can be covered by $n\mathrm{/}(d+1)+1$ vertex-disjoint paths. In fact, our proof gives a partition of $V(G)$ into cycles. We also show that, if $d=\mathrm{\Omega }(n)$ and $G$ is bipartite, then $V(G)$ can be partitioned into $n\mathrm{/}(2d)$ paths (this bound in tight for bipartite graphs).