JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (6): 7-10.doi: 10.6040/j.issn.1671-9352.0.2017.286

Previous Articles     Next Articles

Linear 2-arboricity of graphs with maximum average degree at most 4

ZHANG Jiang-yue, XU Chang-qing*   

  1. School of Science, Hebei University of Technology, Tianjin 300401, China
  • Received:2017-06-06 Online:2018-06-20 Published:2018-06-13

PDF (PC)

628

Abstract: A linear 2-forest is a graph whose components are paths of length at most 2. The linear 2-arboricity of a graph G is the least integer m such that G can be partitioned into m linear 2-forests, denoted by la2(G). The upper bound of the linear 2-arboricity of graph G with mad(G)≤4 is determined and if G is a graph with mad(G)≤4, then la2(G)≤「Δ(G)/2+5 if Δ(G)≡1,2(mod 4)and la2(G)≤「Δ(G)/2+4 if Δ(G)≡0,3(mod 4).

Key words: maximum average degree, linear forest, linear 2-arboricity

CLC Number: 

  • O157
[1] AKIYAMA J. Three developing topics in graph theory[D]. Tokyo: University of Tokyo, 1980.
[2] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs. III: Cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(4):405-417.
[3] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs IV: Linear arboricity[J]. Networks, 1981, 11(1):69-72.
[4] ENOMOTO H, PÉROCHE B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 2010, 8(2):309-324.
[5] GULDAN F. The linear arboricity of 10-regular graphs[J]. Mathematica Slovaca, 1986, 36(3):225-228.
[6] WU J L. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 2015, 31(2):129-134.
[7] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs & Combinatorics, 2003, 19(2):241-248.
[8] 徐常青,安丽莎,杜亚涛.平面图线性2-荫度的一个上界[J]. 山东大学学报(理学版), 2014, 49(4): 38-40. XU Changqing, AN Lisha, DU Yatao. An upper bound on the linear 2-arboricity of planar graph[J]. Journal of Shandong University(Natural Science), 2014, 49(4):38-40.
[9] WANG Y Q. Improved upper bound on the linear 2-arboricity of planar graphs[J]. Discrete in Mathematics, 2016, 339(1):39-45.
[10] XU C Q, CHANG J J. The linear 2-arboricity of some planar graphs[J]. Ars Combinatoria, 2014, 114:223-227.
[11] 吴建良. 图的最大平均度与线性萌度的关系[J]. 山东大学学报(理学版),2005,40(6):27-30. WU Jianliang. The relationship between the maximum average degree and the linear arboricity of a graph[J]. Journal of Shandong University(Natural Science), 2005, 40(6):27-30.
[12] CHEN B L, FU H L, HUANG K C, et al. Decomposing graphs into forests of paths with size less than three[J]. Australasian Journal of Combinatorics, 1991, 3:55-73.
[13] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52(2):123-132.
[1] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[2] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41.
[3] YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13.
[4] CHEN Hong-yu1, ZHANG Li2. The linear 2-arboricity of planar graphs without 5-, 6-cycles with chord [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 26-30.
[5] XU Chang-qing1, AN Li-sha1, DU Ya-tao2. An upper bound on the linear 2-arboricity of planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 38-40.
[6] ZHANG Xin1, XU Lan2, LIU Gui-Zhen1. k-forested coloring of sparse graphs [J]. J4, 2011, 46(4): 1-3.
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