JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (02): 38-42.doi: 10.6040/j.issn.1671-9352.0.2014.324

Previous Articles     Next Articles

On the vertex-arboricity of embedded graphs

SUN Lin1, CAI Hua2   

  1. 1. Department of Mathematics, Changji University, Changji 831100, Xinjiang, China;
    2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2014-07-15 Revised:2014-10-21 Online:2015-02-20 Published:2015-01-27

PDF (PC)

804

Abstract: An induced forest k-partition of a graph G is a k-partition (V1,V2,…,Vk) of the vertex set V(G) such that, for each i with 1≤i≤k, the induced subgraph G[Vi] is a forest. The vertex arboricity of a graph G is the minimum positive integer k such that G has an induced forest k-partition, denoted by va(G). Let G be a simple graph embedded in a surface of nonnegative Euler characteristic, and if G satisfies three kinds of conditions, then va(G)≤2.

Key words: discharging method, vertex arboricity, distance

CLC Number: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976.
[2] CHARTRAND G, KRONK H V, WALL C E. The point-arboricity of a graph[J]. Discrete mathematics, 1968, 6:169-175.
[3] YANG Aifeng, YUAN Jinjiang. On the vertex-arboricity of planar graphs of diameter two[J]. Discrete Mathematics, 2007, 307:2438-2447.
[4] HUANG Danjun, SHIU Wai Chee, WANG Weifan. On the vertex-arboricity of planar graphs without 7-cycles[J]. Discrete Mathematics, 2012, 312:2304-2315.
[5] HUANG Danjun, WANG Weifan. Vertex-arboricity of planar graphs without chordal 6-cycles[J]. International Journal of Computer Mathematics, 2013, 90(2):258-272.
[6] CHEN Min, ANDRE Raspand, WANG Weifan. Vertex-arboricity of planar graphs without intersecting triangles[J]. European Journal of Combinatorics, 2012, 33:905-923.
[7] RASPAND A, WANG Weifan. On the vertex-arboricity of planar graphs[J]. European Journal of Combinatorics, 2008, 29:1064-1075.
[1] SHEN Yunrui, MEI Yinzhen. Resistance distance and Kirchhoff index in graph operation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(4): 92-101.
[2] LI Ji, LIU Aiwen, QIN Liu. Left ventricular MRI segmentation based on nonzero level sets convexity preserving algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 32-47.
[3] CHEN Xu, SHAO Rongxia, WANG Guoping. Distance spectral radius of complements of graphs with cut vertices [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 19-23.
[4] WU Xianxi, HUANG Danjun. Equitable coloring of graphs with mad(G)≤(13)/4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 41-50.
[5] TIAN Shuangliang, CHEN Ping. Distance colorings of the semistrong product and the strong product of paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 167-172.
[6] ZHANG Chunhao, XIE Bin, XU Tongtong, ZHANG Ximei. Density peak clustering algorithm optimized by natural neighbor search [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(1): 29-44.
[7] Miao LIU,Jiayin PENG,Jiangang TANG. Multi-particle short-distance teleportation in noisy environment with weak measurement [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(8): 103-112.
[8] Mengdi LIU,Xianyong ZHANG,Zhiwen MO. A new probabilistic hesitant fuzzy multi-attribute group decision making method based on improved distance measures [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 118-126.
[9] Huan LIU,Huiying QIANG,Hongshen WANG,Yu BAI. 2-distance sum distinguishing coloring of trees [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 47-52, 58.
[10] Zhenai LI,Hui WEI,Xin CHEN. MNSGA-Ⅱ algorithm based on bi-objective for solving nonlinear equation systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(10): 22-29.
[11] Xinglong LUO,Xingshi HE,Jie ZHOU,Xinshe YANG. Improved density peak clustering approach based on African vultures optimization algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(1): 46-55,71.
[12] Yu ZHOU,Ligang ZHOU,Zhichao LIN,Xin XU. Probabilistic q-rung hesitant fuzzy TODIM method and its application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 9-17.
[13] Jin LI,Changqing XU. Adjacent vertex distinguishing edge coloring of IC-planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 134-139.
[14] Shengqiang LIU,Ningjuan MA. Peak value and peak time of nonlinear heterogeneous epidemic model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(10): 1-12.
[15] HAN Lu, GUO Xin-yao, WEI Wei, LIANG Ji-ye. Multi-metric learning algorithm based on constraint hierarchical weighting [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(4): 12-20.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd