Linear k-arboricities on trees

Abstract

For a fixed positive integer k, the linear k-arboricity la(k)(G) of a graph G is the minimum number l such that the edge set E(G) can be partitioned into G disjoint sets and that each induces a subgraph whose components are paths of lengths at most k. This paper studies linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm to determine whether a tree T has la(k)(T)less than or equal to m. (C) 2000 Elsevier Science B.V. All rights reserved.