JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (11): 147-154.doi: 10.6040/j.issn.1671-9352.0.2022.221

Previous Articles     Next Articles

Linear arboricity on embedded graphs without adjacent short cycles

Hongjun DU(),Huijuan WANG*()   

  1. School of Mathematics and Statistics, Qingdao University, Qingdao 266071, Shandong, China
  • Received:2022-04-18 Online:2023-11-20 Published:2023-11-07
  • Contact: Huijuan WANG E-mail:dhjqdu@163.com;sduwhj@163.com

RichHTML

0

PDF (PC)

244

Abstract:

Linear arboricity is an improper edge coloring. The linear arboricity of a graph refers to the minimum number that the edge set is divided into linear forests. By using discharging method, we proved a conclusion about a graph G which can be embedded in a surface of non-negative Euler characteristic with maximum degree Δ≥7. If there exist two fixed integers i, j∈{3, 4, 5, 6} such that G has no adjacent i- cycles or j- cycles, then its linear arboricity is $\left\lceil\frac{\Delta}{2}\right\rceil $.

Key words: Euler characteristic, surface, linear arboricity

CLC Number: 

  • O157.5

Fig.1

The forbidden configurations in G"

Fig.2

Distributions of 3-faces where a 7-vetex is incident with three 3-faces"

Fig.3

Distributions of 3-faces where a 8-vetex is incident with four 3-faces"

1 HARARY F . Covering and packing in graphs Ⅰ[J]. Annals of the New York Academy of Sciences, 1970, 175 (1): 198- 205.
doi: 10.1111/j.1749-6632.1970.tb56470.x
2 AKIYAMA J , EXOO G , HARARY F . Covering and packing in graphs Ⅲ: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30, 405- 417.
3 WU Jianliang . On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31 (2): 129- 134.
doi: 10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A
4 WU Jianliang , WU Yuwen . The linear arboricity of planar graphs of maximum degree seven is four[J]. Journal of Graph Theory, 2008, 58 (3): 210- 220.
doi: 10.1002/jgt.20305
5 CYGAN M , HOU Jianfeng , KOWALIK Ł , et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2011, 69 (4): 403- 425.
6 CHEN Hongyu , TAN Xiang , WU Jianliang , et al. The linear arboricity of planar graphs without 5-, 6-cycles with chords[J]. Graphs and Combinatorics, 2013, 29, 373- 385.
doi: 10.1007/s00373-011-1118-y
7 CHEN Xianglian , WU Jianliang . The linear arboricity of planar graphs without 5-cycles with two chords[J]. Filomat, 2016, 30 (5): 1135- 1142.
doi: 10.2298/FIL1605135C
8 罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23 (2): 113- 119.
LUO Zhaoyang , SUN Lin . The linear arboricity of planar graphs with 6-cycles containing at most one chord[J]. Operations Research Transactions, 2019, 23 (2): 113- 119.
9 WANG Huijuan , LIU Bin , WU Jianliang . The linear arboricity of planar graphs without chordal short cycles[J]. Utilitas Mathematica, 2012, 87, 255- 263.
10 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.
doi: 10.1007/s10878-013-9680-2
11 BONDY J A , MURTY U S R . Graph theory with applications[M]. London: Macmillan Press, 1979.
12 WANG Huijuan , WU Jianliang , LIU Bin , et al. On the linear arboricity of graphs embeddable in surfaces[J]. Information Processing Letters, 2014, 114 (9): 475- 479.
doi: 10.1016/j.ipl.2014.03.013
13 陈洪玲, 王慧娟, 高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 山东大学学报(理学版), 2018, 53 (12): 17- 22.
CHEN Hongling , WANG Huijuan , GAO Hongwei . 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.
14 WU Jianliang , HOU Jianfeng , LIU Guizhen . The linear arboricity of planar graphs with no short cycles[J]. Theoretical Computer Science, 2007, 381, 230- 233.
15 WU Jianliang, HOU Jianfeng, SUN Xiangyong. A note on the linear arboricity of planar graphs without 4-cycles[C]//The Eighth International Symposium on Operations Research and its Applications (ISORA 2009). Beijing, China: World Publishing Corporation, 2009: 174-178.
[1] WANG Shu-juan, YANG Huo-gen, CHAI Ying. Reconstruction of rational polynomial Coons surface patches throuth Bézier triangular geodesic [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 102-110.
[2] WU Feng, ZHANG Liang. Some results on Sasakian statistical manifolds of constant φ -curvature [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(4): 86-93.
[3] 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.
[4] Shu-ren HE,Bin TANG,Xin-feng XING,Chun-ying SHI,Xiu-mei ZHANG,Xiao-mei ZHANG,Xiao-hong XU. Hierarchically porous Au-Cu thin films as catalysts for aerobic oxidation of benzyl alcohol [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 9-17.
[5] LIU Hua-yong, XIE Xin-ping, LI Lu, ZHANG Da-ming, WANG Huan-bao. A class of trigonometric Bézier curve and surface which satisfy G2 continuity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 65-71.
[6] XU Chang-qing1, AN Li-sha1, DU Ya-tao2. An upper bound on the linear 2-arboricity of planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 38-40.
[7] JIN Ming-hao1,2, PEI Dong-he1*. he timelike axis surface of revolution with pointwise 1-type gauss map in Minkowski 3space [J]. J4, 2013, 48(2): 57-61.
[8] DONG Wei-wei. A new method of DEA efficiency ranking for decision making units with independent subsystems [J]. J4, 2013, 48(1): 89-92.
[9] MA Jing-jie. Numerical simulations of the space-fractional Edwards-Wilkinson equation [J]. J4, 2012, 47(9): 121-126.
[10] 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.
[11] YANG Hong-mei ,ZHANG Gui-zhai, LI Xiao-ming*. Distribution characteristics of different forms of nitrogen in  the surface sediments of Nansi Lake [J]. J4, 2012, 47(3): 14-20.
[12] WANG Wen ,MA Xue-qiang,LIU Hong . Computer-aided design of a surface glazing wall based on fractals [J]. J4, 2008, 43(11): 31-35 .
[13] SUN Ting-li and LIU Cheng-bu* . Theoretical study on the mechanism for the reaction of OCS and CN redicals [J]. J4, 2007, 42(5): 44-49 .
[14] YE Hong,ZHAO Wei,FAN Wei-liu,YOU Ting and SUN Si-xiu* . Surface modification of crystalline Mg（OH）2 and its multiple application in EVA [J]. J4, 2007, 42(3): 52-54 .
[15] QU Wen,SU Ji-xin*,PAN Qi,NIE Yu-lun . Synthesis and acid catalytic activity of HSO3-functionalized silica [J]. J4, 2007, 42(11): 11-14 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[2] CHEN Ya-juan1,2, SHANG Xin-chun1*. Dynamical formation and growth of cavity in a heated viscoelastic sphere[J]. J4, 2013, 48(4): 72 -76 .
[3] XU Qiu-yan .

A class of parallel finite difference methods for solving a two-dimensional diffusion equation

[J]. J4, 2008, 43(8): 1 -05 .
[4] YANG Zhao-qiang. A kind of European lookback option pricing model under fractional  jump-diffusion mixed fractional Brownian motion[J]. J4, 2013, 48(6): 67 -74 .
[5] WANG Ting . [J]. J4, 2006, 41(5): 20 -25 .
[6] CAO Yin-hong,GAO Rui . A unicity theorem on the entire function and its linear differential polynomials[J]. J4, 2007, 42(12): 69 -72 .
[7] XUE Qiu-fang1,2, GAO Xing-bao1*, LIU Xiao-guang1. Several equivalent conditions for H-matrix based on the extrapolated GaussSeidel iterative method[J]. J4, 2013, 48(4): 65 -71 .
[8] YU Wei-yan1,2， ZHANG Jian-hua1. Generalized Jordan derivations of full matrix algebras[J]. J4, 2010, 45(4): 86 -89 .
[9] WANG Shun-kang,WANG Lin-shan . Global exponential stability for static neural network models with time-varying delays and Markovian jumping parameters[J]. J4, 2008, 43(4): 81 -84 .
[10] GAO Yun-peng,YAN Jin . Pathfactors with prescribed length in clawfree graphs[J]. J4, 2006, 41(5): 51 -54 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd