On the point linear arboricity of a graph

  • Frank Harary
  • Randall Maddox
  • William Staton

Abstract

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.
Published
1991-05-01
Section
Articoli