JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (6): 25-28, 35.doi: 10.6040/j.issn.1671-9352.0.2023.109

•   • Previous Articles     Next Articles

Linear arboricity in graphs of low treewidth

Hongyu CHEN()   

  1. School of Science, Shanghai Institute of Technology, Shanghai 201418, China
  • Received:2023-03-10 Online:2024-06-20 Published:2024-06-17

RichHTML

1

PDF (PC)

149

Abstract:

Let G=(V, E) be a graph, a map φ from E(G) to {1, 2, …, t} is called a t-linear coloring if the induced subgraph of edges having the same color α is a linear forest for 1≤α≤t. The linear arboricity la(G) is the minimum number t over all t-linear coloring of G. In this paper, we determine $\operatorname{la}(G)=\left\lceil\frac{\Delta}{2}\right\rceil$ for graphs with maximum degree Δ and treewidth at most $\frac{\Delta+1}{4}$.

Key words: linear arboricity, linear coloring, treewidth

CLC Number: 

  • O157.5
1 AKIYAMA J , EXOO G , HARARY F . Covering and packing in graphs III: Cyclic and acyclic invari-ants[J]. Math Slovaca, 1980, 30 (4): 405- 417.
2 AKIYAMA J , EXOO G , HARARY F . Covering and packing in graphs IV: Linear arboricity[J]. Networks, 1981, 11 (1): 69- 72.
doi: 10.1002/net.3230110108
3 ENOMOTO H , PEROCHE B . The linear arboricity of some regular graphs[J]. J Graph Theory, 1984, 8, 309- 324.
doi: 10.1002/jgt.3190080211
4 GULDAN F . The linear arboricity of 10 regular graphs[J]. Math Slovaca, 1986, 36, 225- 228.
5 WU Jianliang . On the linear arboricity of planar graphs[J]. J Graph Theory, 1999, 31, 129- 134.
doi: 10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A
6 WU Jianliang , WU Yuwen . The linear arboricity of planar graphs of maximum degree seven are four[J]. J Graph Theory, 2008, 58, 210- 220.
doi: 10.1002/jgt.20305
7 WU Jianliang . The linear arboricity of series-parallel graphs[J]. Graphs Combin, 2000, 16 (3): 367- 372.
doi: 10.1007/s373-000-8299-9
8 吴建良. Halin图的一些路分解[J]. 山东矿业学院学报, 1998, 17 (1): 92- 96.
WU Jianliang . Some path decompositions of Halin graphs[J]. Journal of Shandong Mining Institute, 1998, 17 (1): 92- 96.
9 BODLAENDER H L . A partial k-arboretum of graphs with bounded treewidth[J]. Theor Comput Sci, 1998, 209 (12): 1- 45.
10 BODLAENDER H L. Planar graphs with bounded treewidth[D]. Utrecht: University of Utrecht, 1988.
11 CHEN Hongyu , LAI Hongjian . On the linear arboricity of graphs with treewidth at most four[J]. Graphs and Combinatorics, 2023, 39, 1- 15.
doi: 10.1007/s00373-022-02594-9
12 DIESTEL R . Graph Theory[M]. New York: Springer-Verlag, 2010.
13 LANG R. On the list chromatic index of graphs of tree-width 3 and maximum degree at least 7[EB/OL]. (2015-04-08) [2022-12-10]. http://arxiv.org/pdf/1504.02122.
14 MEEKS K , SCOTT A . The parameterised complexity of the list problems on graphs of bounded treewidth[J]. Inform Comput, 2016, 251, 91- 103.
doi: 10.1016/j.ic.2016.08.001
15 BRUHN H , LANG R , STEIN M . List edge-coloring and total coloring in graphs of low treewidth[J]. J Graph Theory, 2016, 81 (3): 272- 282.
doi: 10.1002/jgt.21874
16 陈洪玲, 王慧娟, 高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 山东大学学报(理学版), 2018, 53 (12): 17- 22.
doi: 10.6040/j.issn.1671-9352.0.2017.539
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.
doi: 10.6040/j.issn.1671-9352.0.2017.539
17 张江悦, 徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报(理学版), 2018, 53 (6): 7- 10.
doi: 10.6040/j.issn.1671-9352.0.2017.286
ZHANG Jiangyue , XU Changqing . Linear 2-arboricity of graphs with maximum average degree at most 4[J]. Journal of Shandong University (Natural Science), 2018, 53 (6): 7- 10.
doi: 10.6040/j.issn.1671-9352.0.2017.286
18 BRUHN H , GELLERT L , LANG R . Chromatic index, treewidth and maximum degree[J]. Electronic Journal of Combinatorics, 2018, 25 (2): 2- 23.
19 HAN Miaomiao , LU You , LUO Rong , et al. Neighbor sum distinguishing total coloring of graphs with bounded treewidth[J]. J Comb Optim, 2018, 36, 23- 34.
doi: 10.1007/s10878-018-0271-0
[1] 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.
[2] 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.
[3] 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WU Hong-bo,QIAO Xi-min, . The ∑Γ－fuzzy truth degree of formula relative to the finite theory in propositional logic system Ln[J]. J4, 2008, 43(6): 1 -8 .
[2] SUI Yunyun. The distribution of propositional truth degree in 5valued logic systems
associated with a nonlinear ordering true value set
[J]. J4, 2009, 44(1): 78 -82 .
[3] WU Peng-fei,MENG Xiang-zeng,LIU Jun-xiao,MA Feng-juan . Structure and content-based extraction of topical information from Web pages[J]. J4, 2006, 41(3): 131 -134 .
[4] MA Xin-guang. An integral-type operator from the Dirichlet  space to the Bloch-type space[J]. J4, 2012, 47(4): 66 -69 .
[5] YAN Wei-rong, HONG Yu, ZHU Shan-shan, CHE Ting-ting, YAO Jian-min, ZHU Qiao-ming. Method of implicit discourse relation detection based on semantics scenario[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(11): 59 -67 .
[6] ZHU Meng-jun,JIANG Hong-xun*,XU Wei. Weibo moods and propagation factors based stock prices prediction[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(11): 13 -25 .
[7] . Irreducible representations of D(kS3) and ring structure of its Grothendieck group[J]. J4, 2009, 44(12): 17 -21 .
[8] . The optimized algorithm of optical threedimensional 
measurement for phaseshift technique[J]. J4, 2009, 44(6): 40 -45 .
[9] HU Li-xia, ZHANG Jian-hua. Lie higher derivable mappings of triangular algebras at zero points[J]. J4, 2013, 48(4): 5 -9 .
[10] LI Ying, SONG Wei-dong. On pseudo-umbilical timelike submanifold in a de Sitter space[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 64 -67 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd