JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (12): 36-41.doi: 10.6040/j.issn.1671-9352.0.2016.597

Previous Articles     Next Articles

Linear 2-arboricity of planar graphs with 4-cycles have no common vertex

CHEN Hong-yu1, ZHANG Li2   

  1. 1. School of Science, Shanghai Institute of Technology, Shanghai 201418, China;
    2. School of Statistics and Mathematics, Shanghai Lixin University of Accouting and Finance, Shanghai 201209, China
  • Received:2016-12-16 Online:2017-12-20 Published:2017-12-22

PDF (PC)

1251

Abstract: The linear 2-arboricity la2(G)of G is the least integer k to divide G into k edge-disjoint forests, and each branch of the forests is a path with the length at most 2. We prove that if G is a planar graph with 4-cycles without common vertex, then la2(G)≤「Δ/2+5.

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

CLC Number: 

  • O157.5
[1] HABIB M, PEROCHE B. Some problems about linear arboricity[J]. Discrete Mathematics, 1982, 41(2):219-220.
[2] CHEN B L, FU H L, HUANG K C. Decomposing graphs into forests of paths with size less than three[J]. Australas J Combin, 1991, 3:55-73.
[3] FU H L, HUANG K C. The linear 2-arboricity of complete bipartite graphs[J]. Ars Combinatoria, 1994, 38:309-318.
[4] THOMASSEN C. Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J]. Journal of Combinatorial Theory, 1999, 75(1):100-109.
[5] CHANG G J. Algorithmic aspects of linear k-arboricity[J]. Taiwanese Journal of Mathematics, 1999, 3(1):73-81.
[6] CHANG G J, CHEN B L, FU H L, et al. Linear k-arboricity on trees [J]. Discrete Appl Math, 2000, 103:281-287.
[7] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity [J]. Discrete Math, 1984, 52: 123-132.
[8] JACKSON B, WORMALD N C. On the linear k-arboricity of cubic graphs[J]. Discrete Mathematics, 1996, 162(1-3):293-297.
[9] ALDRED R E L, WORMALD N C. More on the linear k-arboricity of regular graphs[J]. Australasian Journal of Combinatorics, 2014, 18:97-104.
[10] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs & Combinatorics, 2003, 19(2):241-248.
[11] 钱景,王维凡. 不含4-圈的平面图的线性2-荫度[J].浙江师范大学学报(自然科学版),2006,29(2):121-125. QIAN Jing, WANG Weifan. The linear 2-arboricity of planar graphs without 4-cycles[J]. J Zhejiang Norm Univ(Nat Sci), 2006, 29(2): 121-125.
[12] MA Qin, WU Jianliang. Planar graphs without 5-cycles or without 6-cycles [J]. Discrete Math, 2009, 309: 2998-3005.
[13] CHEN Hongyu, TAN Xiang, WU Jianliang. The linear 2-arboricity of planar graphs without adjacent short cycles [J]. Bull Korean Math Soc, 2012, 49: 145-154.
[14] 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版),2012,47(6):71-75. WANG Ranqun, ZUO Liancui. The linear 2-arboricity of planar graphs without 4-cycles and 5-cycles[J]. Journal of Shandong University(Natural Science), 2012, 47(6): 71-75.
[15] 陈宏宇, 张丽. 不含弦5-圈和弦6-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2014, 49(6):26-30. CHEN Hongyu, ZHANG Li. The linear 2-arboricity of planar graphs without 5-, 6-cycles with chord[J]. Journal of Shandong University(Natural Science), 2014, 49(6):26-30.
[1] GAO Wei, NI Guanqun. Cooperation strategy between retailers and community group buying platforms considering the time sensitive differences of consumers [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 99-109.
[2] BAI Yu, QIANG Huiying, HE Jing. Neighbor sum distinguishing edge coloring of join graphs Cm∨Cn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 161-166.
[3] Lianjie ZHANG,Wei LI,Ping YANG,Min ZENG,Qiuwang WANG. Effect of PCM-PCHE on SCO2 Brayton cycle under variable operating conditions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(11): 74-84.
[4] 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.
[5] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[6] MA Li-li, WU Di, LI Qiang, XU Jing. On Abelian extensions of Hom-δ-Jordan Lie triple systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 1-5.
[7] MA Li-li, DAI Di, LI Qiang. Constitutions and Abelian extensions of δ-Jordan Lie supertriple systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(8): 76-80.
[8] YANG Han, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total colorings and vertex-distinguishing Ⅵ-total colorings of mC7 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 76-82.
[9] TAN Xiang. Total colorings of one type of planar graphs with maximum degree 6 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 71-75.
[10] LIU Zhuo-ya, XU Chang-qing. Adjacent vertex distinguishing edge coloring of planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(9): 36-41.
[11] MA Li-li, LI Qiang. Abelian extensions of δ-Lie color algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(8): 38-42.
[12] CHEN Hong-yu, ZHONG Bin. Linear 2-arboricity of planar graphs without intersecting 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 38-45.
[13] CHEN Chen, GAO Ying-ying, CHEN Hui-xiang. Lazy 2-cocycles on 9-dimensional Taft algebra [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(2): 73-78.
[14] 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.
[15] CHEN Hong-ling, WANG Hui-juan, GAO Hong-wei. Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 17-22.
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