Vertex Arboricity of Toroidal Graphs with a Forbidden Cycle

Abstract

The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$, it is known that $a(G)\le 3$. In two recent papers, it was proved that planar graphs without $k$-cycles for some $k\in \{3,4,5,6,7\}$ have vertex arboricity at most 2. For a toroidal graph $G$, it is known that $a(G)\le 4$. Let us consider the following question: do toroidal graphs without $k$-cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$. Since a complete graph on 5 vertices is a toroidal graph without any $k$-cycles for $k\ge 6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.

arXiv comment8 pages, 2 figures