Title

Vertex arboricity of graphs embedded in a surface of non-negative Euler characteristic.

Authors

Teng, Wenshun; Wang, Huijuan

Abstract

The vertex arboricity 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 Σ of Euler characteristic χ (Σ) ≥ 0. We prove that for the graph G which can be embedded in a surface Σ of Euler characteristic χ (Σ) ≥ 0 if no 3 -cycle intersects a 5 -cycle, or no 5 -cycle intersects a 6 -cycle, then va (G) ≤ 2 in addition to the 4 -regular quadrilateral mesh.

Subjects

EULER characteristic; GRAPH coloring; PLANAR graphs

Publication

Discrete Mathematics, Algorithms & Applications, 2020, Vol 12, Issue 06, pN.PAG

ISSN

1793-8309

Publication type

Academic Journal

DOI

10.1142/S1793830920500809