Le Matematiche (Oct 1989)

On the point linear arboricity of a graph

  • Frank Harary,
  • Randall Maddox,
  • William Staton

Journal volume & issue
Vol. 44, no. 2
pp. 281 – 286

Abstract

Read online

In a linear forest, every component is a path. The linear arboricity of a graph G is the smallest number of edge disjoint linear forests whose union is G; this concept has been much studied. We now introduce the point linear arboricity of G, defined as the smallest number of parts in a partition of V=V(G) such that each part induces a linear forest. We prove an analogue to the classical theorem of Brooks for the invariant.