Vertex Arboricity of Toroidal Graphs with a Forbidden Cycle

Original · EN

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)≤ 3. In two recent papers, it was proved that planar graphs without k-cycles for some k∈{3, 4, 5, 6, 7} have vertex arboricity at most 2. For a toroidal graph G, it is known that a(G)≤ 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≥ 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.