The Vertex Linear Arboricity of Claw-Free Graphs with Small Degree

Abstract

The vertex linear arboricity $vla(G)$ of a 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. It is proved here that $\lceil \frac{\omega (G)}{2}\rceil \le vla(G)\le \lceil \frac{\omega (G)+1}{2}\rceil$ for a claw-free connected graph $G$ having $\mathrm{\Delta }(G)\le 6$, where $\omega (G)$ is the clique number of $G$.