Narrow Results

The vertex arboricity $\mathrm{\text{va}}(G)$ of a graph $G$ is the minimum number of colors the vertices of the graph $G$ can be colored so that every color class induces an acyclic subgraph of $G$. There are many results on the vertex arboricity of planar graphs. In this paper, we replace planar graphs with graphs which can be embedded in a surface $\mathrm{\Sigma }$ of Euler characteristic $\chi (\mathrm{\Sigma })\ge 0$. We prove that for the graph $G$ which can be embedded in a surface $\mathrm{\Sigma }$ of Euler characteristic $\chi (\mathrm{\Sigma })\ge 0$ if no $3$-cycle intersects a $5$-cycle, or no $5$-cycle intersects a $6$-cycle, then $\mathrm{\text{va}}(G)\le 2$ in addition to the $4$-regular quadrilateral mesh.