ALGORITHMIC ASPECTS OF LINEAR k-ARBORICITY
Gerard J. Chang · 1999
Abstract. For a fixed positive integer k, the linear k-arboricity lak(G) of a graph G is the minimum number ℓ such that the edge set E(G) can be partitioned into ℓ disjoint sets, each induces a subgraph whose components are paths of lengths at most k. This paper examines linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm for determining whether a tree T has la2(T) ≤ m. We also give a characterization for a tree T with maximum degree 2m having la2(T) = m. 1.