JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (12): 17-22.doi: 10.6040/j.issn.1671-9352.0.2017.539

Previous Articles     Next Articles

Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic

CHEN Hong-ling, WANG Hui-juan*, GAO Hong-wei   

  1. School of Mathematics and Statistics, Qingdao University, Qingdao 266071, Shandong, China
  • Online:2018-12-20 Published:2018-12-18

PDF (PC)

614

Abstract: The linear arboricity of graph G, denoted by la(G), is the minimum number of linear forest required to partition the edge set E(G), which is an improper edge coloring. The linear arboricity of graph which can be embedded in a surface of non-negative Euler characteristic with maximum Δ(G)≥7 is mainly studied. If there is no adjacent chordal 6-cycle, then the arboricity of graph G is「Δ/2.

Key words: Euler characteristic, linear forest, cycle

CLC Number: 

  • O157.5
[1] FRANK H. Covering and packing in graphs, I.[J]. Annals of the New York Academy of Sciences, 2010, 175(1):198-205.
[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] WU J L, LIU G, WU Y W. The linear arboricity of composition graphs[J]. Journal of Systems Science & Complexity, 2002, 15(4):38-41.
[4] WU Jianling. The linear arboricity of Series-Parallel graphs[J]. Graphs & Combinatorics, 2000, 16(3):367-372.
[5] JIN A, EXOO G, HARARY F. Covering and packing in graphs IV: linear arboricity[J]. Networks, 2010, 11(1):69-72.
[6] ENMOTO H, PEROCHE B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 1984, 8(2):309-324.
[7] GULDAN F. The linear arboricity of 10 regular graph[J]. Mathematical Institute of the Slovak Academy of Sciences, 1986, 36(3):225-228.
[8] WU Jianliang. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31(2):129-134.
[9] WU Jianliang, WU Yuwen. The linear arboricity of planar graphs of maximum degree seven are four[J]. Journal of Graph Theory, 2008, 58(3):210-220.
[10] CYGAN M, HOU J, KOWALIK L, et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2012, 69(4):403-425.
[11] WANG Huijuan, WU Lidong, WU Weili, et al. Minimum number of disjoint linear forests covering a planar graph[J]. Journal of Combinatorial Optimization, 2014, 28(1):274-287.
[12] ALON N. The linear arboricity of graphs[J]. Israel Journal of Mathematics, 1988, 62(3):311-325.
[13] WU Jianliang, HOU Jianfeng, SUN Xiangyong. A note on the linear arboricity of planar graphs without 4-cycles[J]. The Eighth International Symposium on Operations Research and Its Applications, 2009, 09:174-178.
[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] Hongjun DU,Huijuan WANG. Linear arboricity on embedded graphs without adjacent short cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 147-154.
[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] MA Li-li, LI Qiang. Abelian extensions of δ-Lie color algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(8): 38-42.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
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