Upper bounds on linear vertex-arboricity of complementary graphs

Abstract

The linear vertex-arboricity ρ(G) of a gragh G is defined to be the minimum number of subsets into which the vertex set of G can be partitioned such that each subset induces a linear forest. Alavi et.al. [1] gave sharp upper and lower bounds for the sum and product of linear vertex-arboricity of a graph and its complement. In this paper we give an improved upper bound for that sum.