Research PaperNo Access

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

Wenshun Teng

School of Mathematics and Statistics, Qingdao University, Qingdao 266071, P. R. China

E-mail Address: twsqdu@163.com

Search for more papers by this author

and

Huijuan Wang

School of Mathematics and Statistics, Qingdao University, Qingdao 266071, P. R. China

E-mail Address: sduwhj@163.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S1793830920500809Cited by:0 (Source: Crossref)

Abstract

The vertex arboricity $va (G)$ $va (G)$ of a graph $G$ $G$ is the minimum number of colors the vertices of the graph $G$ $G$ can be colored so that every color class induces an acyclic subgraph of $G$ $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 $χ (Σ) \geq 0$ $χ (Σ) \geq 0$ . We prove that for the graph $G$ $G$ which can be embedded in a surface $Σ$ $Σ$ of Euler characteristic $χ (Σ) \geq 0$ $χ (Σ) \geq 0$ if no $3$ $3$ -cycle intersects a $5$ $5$ -cycle, or no $5$ $5$ -cycle intersects a $6$ $6$ -cycle, then $va (G) \leq 2$ $va (G) \leq 2$ in addition to the $4$ $4$ -regular quadrilateral mesh.

Keywords:

AMSC: 05C15

References

1. H. Cai, J. Wu and L. Sun, Vertex arboricity of planar graphs without intersecting 5-cycles, J. Comb. Optim. 35(2) (2018) 365–372. Crossref, Google Scholar
2. G. Chartrand and H. V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612–616. Crossref, Google Scholar
3. G. Chartrand, H. V. Kronk and C. E. Wall, The point-arboricity of a graph, Israel J. Math. 6(2) (1968) 169–175. Crossref, Google Scholar
4. M. Chen, A. Raspaud and W. Wang, Vertex-arboricity of planar graphs without intersecting trangles, Eur. J. Combin. 33(5) (2012) 905–923. Crossref, Google Scholar
5. H. L. Chen, W. S. Teng, H. J. Wang and H. W. Gao, Vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles, Sch. J. Phys. Math. Statist. 5(10) (2018) 322–327. Google Scholar
6. I. Choi and H. Zhang, Vertex arboricity of toroidal graphs with a forbidden cycle, Discrete Math. 333 (2014) 101–105. Crossref, Google Scholar
7. G. Fijavz̆, M. Juvan, B. Mohar and R. S̆krekovski, Planar graphs without cycles of specific lengths, Eur. J. Combin. 23(4) (2002) 377–388. Crossref, Google Scholar
8. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman and Company, New York, 1979). Google Scholar
9. D. Huang, W. C. Shiu and W. Wang, On the vertex-arboricity of planar graphs without 7-cycles. Discrete Math. 312(15) (2012) 2304–2315. Crossref, Google Scholar
10. D. Huang and W. F. Wang, Vertex-arboricity of planar graphs without chordal 6-cycles, Int. J. Comput. Math. 90(2) (2013) 258–272. Crossref, Google Scholar
11. A. Raspaud and W. Wang, On the vertex-arboricity of planar graphs, Eur. J. Combin. 29(4) (2008) 1064–1075. Crossref, Google Scholar
12. W. Teng, H. Wang, H. Chen and B. Liu, Social structure decomposition with security issue, IEEE Access 7 (2019) 82785–82793. Crossref, Google Scholar
13. W. Wang and K. W. Lin, Choosability and edge choosability of planar graphs without five cycles, Appl. Math. Lett. 15(4) (2002) 561–565. Crossref, Google Scholar