Decompositions into two linear forests of bounded lengths

Zusammenfassung

For some k∈𝕫≥0U{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,l)-bounded linear forest decomposition of a graph G is a partition of e(G) into the edge sets of two linear forests Fk, Fl where Fk is k-bounded and Fl is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k ≥ 9 and l = 1, and is in P for (k, l) = (2,1). Before this, the only known NP-complete cases were the (2,3) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-coloring such graphs.