Vertex-arboricity of toroidal graphs without K5- and 6-cycles

The vertex-arboricity upsilon a(G) of a graph G is defined to be the minimum number of colors needed to color the vertices of G such that no cycle is monochromatic. The list vertex-arboricity upsilon a(l)(G) is the list-coloring version of this concept. In this paper, we prove that every toroidal graph G with neither K-5(-) (a K-5 missing at most one edge) nor 6-cycles satisfies upsilon a(l) (G) <= 2. This will be best possible in the sense that forbidding only one of the two structures cannot guarantee its (list) vertex-arboricity being at most 2. (C) 2021 Elsevier B.V. All rights reserved.