Algorithmic aspects of linear \(k\)-arboricity (Q1301997): Difference between revisions

For a graph \(G\), \(\text{la}_2(G)\) denote the smallest number \(\ell\) such that the edge set of \(G\) can be partitioned into \(\ell\) disjoint sets, each of which forms a subgraph whose components are paths consisting of one or two edges. The author points out, by giving a counterexample, that the characterization of trees \(T\) of maximum degree \(2m\) and \(\text{la}_2(T)=m\), given in \textit{M. Habib} and \textit{B. Péroche} [Ann. Discrete Math. 17, 307-317 (1983; Zbl 0523.05025)], is incorrect. The author gives a correct characterization for such trees and, moreover, a linear time algorithm that tests, for a given tree \(T\) and an integer \(m > 0\), whether or not \(\text{la}_2(T)\leq m\).