On the linear vertex arboricity of graphs

Abstract

The minimum number of subsets into which the vertex-set of a graph can be partitioned so that every subset induces a linear forest is defined as the linear-vertex arboricity of the graph. The linear-vertex arboricity of various classes of simple graphs are determined. In particular, the joins of various types of graphs turn out to provide nice structures that are related to their linear vertex arboricity. The characterization of maximally critical graphs (graphs of which the linear vertex arboricity increases with the addition of any edge which belongs to their complements) was completely established. Some general characterizations of minimally critical graphs (graphs of which the linear vertex arboricity decreases with the deletion of any edge) and various classes of minimally critical graphs were established. It was found that for graphs of order less than 8, these classes are the only ones. The results also confirmed that complete graphs of odd order are the only class of critical graphs (graphs which are both maximally and minimally critically).