This note provides a new perspective, i.e., graph embeddings on the decycling number\(\nabla (G)\) (Beineke and Vandell in J Graph Theory 25:59–77,1997) of a graphG. For this point, it is shown that\(\nabla (G)=\gamma _M(G)+\xi (G)\) for any cubic graphG and\(|S|=\frac{\beta (G)+m(S)}{k-1}\) for any decycling setS of ak-regular graphG, where\(\gamma _M(G)\),\(\xi (G)\),\(\beta (G)\) and\(m(S)=c(G-S)+|E(S)|-1\) (\(c(G-S)\) is the number of components of\(G-S\) and |E(S)| is the number of edges in a subgraphG[S]) are, respectively, the maximum genus, the Betti deficiency (Xuong in J Combin Theory Ser B 26:217–225,1979), the cycle rank (Harary in Graph theory, Academic Press, New York,1967) and the margin number ofG. Meanwhile, we further confirm that (1) a cubic graphG (\(G\ne K_4\)) has a vertex partition\((V_1, V_2)\) such that\(V_1\) is an independent set and\(V_2\) induces a forest and (2) ak-regular graphG with\(\nabla (G)=\frac{\beta (G)+m(S)}{k-1}\) (\(m(S)\le 2\)) has a vertex partition\((S,G-S)\) such thatG[S] contains at most two edges and\(G-S\) induces a forest, whereS is the smallest decycling set ofG. Resorting to the above vertex partitions, we get the adjacent vertex distinguishing (AVD) total chromatic numbers of some families of graphs, and these results verify Zhang’s conjecture (Zhang in Sci China Ser A 48:289–299,2005) that every graph with maximum degree\(\Delta \) has an AVD-total\((\Delta +3)\)-coloring.

The authors would like to thank the anonymous referees for their valuable and constructive suggestions, which greatly improve the present paper. Supported by the National Natural Science Foundation of China under Grant Nos. 11171114, 11401576; Science and Technology Commission of Shanghai Municipality under Grant No. 13dz2260400

Authors and Affiliations

1. School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai, 201620, People’s Republic of China

   Chao Yang

2. Department of Mathematics, East China Normal University, Shanghai, 200241, People’s Republic of China

   Han Ren

3. Shanghai Key Laboratory of PMMP, Shanghai, 200241, People’s Republic of China

   Han Ren

4. Department of Mathematics, Renmin University of China, Beijing, 100872, People’s Republic of China

   Erling Wei

Corresponding author

Correspondence toChao Yang.

Reprints and permissions