Efficient Algorithms for Path Partitions

An [a. b] path partition is a decomposition of the edges of a graph into a independent path sets and b matchings, where an independent path set is a set of paths that do not interesect each other. The path partition problem is related to other edge partition problems, such as edge coloring. It is shown that every graph with maximum degree 3 has a [2,0] path partition, and every graph with maximum degree 4 has a [2,1] path partition. Algorithmic proofs are given. The algorithms have linear-time sequential implementations and log - time parallel implementations.
Note: Abstract extracted from PDF file via OCR

Williams, Craig, and Dana Richards. "Efficient Algorithms for Path Partitions." University of Virginia Dept. of Computer Science Tech Report (1987).