JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)

Previous Articles     Next Articles

An upper bound on the linear 2-arboricity of planar graph

XU Chang-qing1, AN Li-sha1, DU Ya-tao2   

  1. 1. Department of Applied Mathematics, Hebei University of Technology, Tianjin 300401, China;
    2. Department of Basic Courses, Ordnance Engineering College, Shijiazhuang 050003, Hebei, China
  • Received:2013-06-18 Online:2014-04-20 Published:2014-06-03

Abstract: Let G be a planar graph with maximum degree Δ.  The linear 2-arboricity of G is the least integer k such that G can be partitioned into k edge disjoint forests, whose component trees are paths of length at most 2. It is denoted by la2(G). We get that la2(G)≤「Δ/2-+8 if Δ≡0,3(mod 4) and la2(G)≤「Δ/2-+7 if Δ≡1,2(mod 4).

Key words: linear arboricity, planar graph, linear 2-arboricity

[1] ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.
[2] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.
[3] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[4] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.
[5] 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.
[6] TAN Xiang. Total colorings of planar graphs without 6-cycles and adjacent 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 72-78.
[7] ZHU Hai-yang, GU Yu, LÜ Xin-zhong. New upper bound on the chromatic number of the square of a planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 94-101.
[8] MENG Xian-yong, GUO Jian-hua, SU Ben-tang. The complete coloring of 3-regular Halin graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 127-129.
[9] MA Gang. Acyclic list edge coloring of planar graphs with girth #br# ≥ 11 and maximum degree 3 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(2): 18-23.
[10] 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.
[11] ZHANG Jia-li, MIAO Lian-ying, SONG Wen-yao. Edge colorings of 1-planar graphs for maximum degree eight #br# without adjacent 4-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 18-23.
[12] ZHU Hai-yang1, CHEN Wei1, L Xin-zhong2, LI Pei-jun3. On L(p,q)-labeling of planar graphs without 4,5,6-cycles and intersecting triangles [J]. J4, 2013, 48(4): 28-34.
[13] XUE Ling1, WU Jian-liang2*. Total chromatic number of planar graphs with few short cycles [J]. J4, 2012, 47(9): 84-87.
[14] WANG Ran-qun, ZUO Lian-cui. The linear 2-arboricity of plane graphs without 4-cycles and 5-cycles [J]. J4, 2012, 47(6): 71-75.
[15] DING Wei. Acyclic edge coloring of planar graphs without 4-Cycles [J]. J4, 2012, 47(6): 76-79.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!