Algorithmic aspects of linear k-arboricity

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 l 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 la(2)(T) less than or equal to m. We also give a characterization for a tree T with maximum degree 2m having la(2)(T) = m.