On the Linear Vertex-Arboricity of a Surface

Abstract

The linear vertex-arboricity of a surface $S$ is the maximum of the linear vertex-arboricities of all graphs embeddable into $S$. Poh showed that the linear vertex-arboricity of a sphere is three. We show that the linear vertex-arboricities of a projective plane and a torus are three and four, respectively. Moreover, we show that the linear vertex-arboricity of a Klein bottle is three or four.