JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2020, Vol. 55 ›› Issue (7): 38-45.doi: 10.6040/j.issn.1671-9352.0.2019.095

Previous Articles    

Linear 2-arboricity of planar graphs without intersecting 5-cycles

CHEN Hong-yu, ZHONG Bin   

  1. School of Science, Shanghai Institute of Technology, Shanghai 201418, China
  • Published:2020-07-08

PDF (PC)

324

Abstract: Let G be a planar graph without intersecting 5-cycles. If G is connected and δ(G)≥2, then G contains an edge xy with d(x)+d(y)≤10 or a 2-alternating cycle is proved. By this result, its linear 2-arboricity la2(G)≤「Δ/2+5 is obtained, which improves the known upper bound of la2(G) for planar graphs without 5-cycles.

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

CLC Number: 

  • O5
[1] HABIB M, PÉRROCHE B. Some problems about linear arboricity[J]. Discrete Math, 1982, 41: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]. Australas J Combin, 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 Series B, 1999, 75(1):100-109.
[5] CHANG G J, CHEN B L, FU H L, et al. Linear k-arboricities on trees[J]. Discrete Applied Mathematics, 2000, 103(1/2/3):281-287.
[6] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52(2):123-132.
[7] JACKSON B, WORMALD N C. On the linear k-arboricity of cubic graphs.[J]. Discrete Mathematics, 1996, 162(1/2/3):293-297.
[8] ALDRED R E L, WORMALD N C. More on the linear k-arboricity of regular graphs[J]. Australasian Journal of Combinatorics, 1998, 18:97-104.
[9] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs and Combinatorics, 2003, 19:241-248.
[10] 钱景,王维凡. 不含4-圈的平面图的线性2-萌度[J]. 浙江师范大学学报(自然科学版)2006, 29(2): 121-125. QIAN Jing, WANG Weifan. The linear 2-arboricity of planar graphs without 4-cycles[J]. Journal of Zhejiang Normal University(Nat Sci), 2006, 29:121-125.
[11] MA Qin, WU Jianliang. Planar graphs without 5-cycles or without 6-cycles[J]. Discrete Mathematics, 2009, 309:2998-3005.
[12] CHEN Hongyu, TAN Xiang, WU Jianliang. The linear 2-arboricity of planar graphs without adjacent short cycles[J]. Bull Korean Math Soc, 2012, 49(1):145-154.
[13] 王苒群,左连翠. 不含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.
[14] 陈宏宇,张丽. 不含弦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.
[15] NIU H X, CAI J S. Linear 2-Arboricity of planar graphs with neither 3-cycles nor adjacent 4-cycles[J]. Graphs and Combinatorics, 2013, 29(3):661-667.
[16] WANG W, LI Y, HU X, et al. Linear 2-arboricity of toroidal graphs[J/OL]. Bulletin of the Malaysian Mathematical Sciences Society, 2016. DOI: 10.1007/s40840-016-0434-z(2016).
[1] 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.
[2] 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.
[3] LI Qiang, MA Li-li, WANG Xiao-yan, LYU Li-jiao. Abelian extensions of Hom-Jordan Lie algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 4-8.
[4] 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.
[5] LIU Jia, SUN Lei. Planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 31-40.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30.
[11] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43.
[12] 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.
[13] BAI Dan, ZUO Lian-cui. The(d,1)-total labelling of the cube of cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 59-64.
[14] WANG Jia-jiang, CHEN Ling, MEN Yu-tao, JI Chen. The feasibility study on shorten treatment cycle of dental implantation and split-root technique joint repair [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(3): 40-43.
[15] 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.
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