We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- 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