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)

456

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] 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] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43.
[9] 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.
[10] 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.
[11] 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.
[12] WU Zi-juan, CHEN Yuan-yuan, ZHANG Liang-yun. Quasidimodule algebras over Hopf quasigroups and Yetter-Drinfeld quasimodule algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 28-33.
[13] XUE Li-xia, LI Zhi-hui, XIE Jia-li. A note on the optimal information rate of hypercycle access structure with three hyperedges [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(11): 60-66.
[14] WANG Shan-shan, QI En-feng. On the number of contractible edges of longest cycles in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 27-31.
[15] MENG Xian-qing. Strong edge coloring of a class of planar graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(08): 10-13.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
[2] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[3] SUN Xiao-ting1, JIN Lan2*. Application of DOSY in oligosaccharide mixture analysis[J]. J4, 2013, 48(1): 43 -45 .
[4] YANG Lun, XU Zheng-gang, WANG Hui*, CHEN Qi-mei, CHEN Wei, HU Yan-xia, SHI Yuan, ZHU Hong-lei, ZENG Yong-qing*. Silence of PID1 gene expression using RNA interference in C2C12 cell line[J]. J4, 2013, 48(1): 36 -42 .
[5] YANG Ying, JIANG Long*, SUO Xin-li. Choquet integral representation of premium functional and related properties on capacity space[J]. J4, 2013, 48(1): 78 -82 .
[6] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[7] YANG Yong-wei1, 2, HE Peng-fei2, LI Yi-jun2,3. On strict filters of BL-algebras#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 63 -67 .
[8] ZHAO Tong-xin1, LIU Lin-de1*, ZHANG Li1, PAN Cheng-chen2, JIA Xing-jun1. Pollinators and pollen polymorphism of  Wisteria sinensis (Sims) Sweet[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 1 -5 .
[9] TANG Xiao-hong1, HU Wen-xiao2*, WEI Yan-feng2, JIANG Xi-long2, ZHANG Jing-ying2, SHAO Xue-dong3. Screening and biological characteristics studies of wide wine-making yeasts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 12 -17 .
[10] WANG Bi-yu, CAO Xiao-hong*. The perturbation for the Browder’s theorem of operator matrix#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 90 -95 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd