Bounds for the vertex linear arboricity
Makoto Matsumoto · Journal of Graph Theory · 1990
Abstract The vertex linear arboricity vla(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are paths. This paper provides an upper bound for vla(G) of a connected nonempty graph G, namely vla(G) ≦ 1 + ⌊δ(G)/2⌋ where δ(G) denotes the maximum degree of G. Moreover, if δ(G) is even, then vla(G) = 1 + ⌊δ(G)/2⌋ if and only if G is either a cycle or a complete graph.