Path decompositions of regular graphs with prescribed girth

A Pℓ-decomposition of a graph G is a set of pairwise edge-disjoint paths of G with ℓ edges that cover the edge set of G. Kotzig [Kotzig, A., Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades, Časopis Pěst. Mat. 82 (1957), pp. 76–92.] proved that a 3-regular graph admits a P3-decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an ℓ-regular graph to admit a Pℓ-decomposition, for odd ℓ. Let g, ℓ and m be positive integers with g≥3. We prove that, (i) if ℓ is odd and m>2⌊(ℓ−2)/(g−2)⌋, then every mℓ-regular graph with girth at least g that contains an m-factor admits a Pℓ-decomposition; (ii) if m>⌊(ℓ−2)/(g−2)⌋, then every 2mℓ-regular graph with girth at least g admits a Pℓ-decomposition.