您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (6): 25-28, 35.doi: 10.6040/j.issn.1671-9352.0.2023.109

•   • 上一篇    下一篇

树宽较小的图的线性荫度

陈宏宇()   

  1. 上海应用技木大学理学院, 上海 201418
  • 收稿日期:2023-03-10 出版日期:2024-06-20 发布日期:2024-06-17
  • 作者简介:陈宏宇(1981—)，女，副教授，博士，研究方向为图论. E-mail: hongyuchen86@126.com
  • 基金资助:
    国家自然科学基金青年科学基金资助项目(11401386);上海应用技术大学中青年科技人才发展基金项目

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)

201

摘要：

设G=(V, E)为一个图, 如果染相同颜色α的边导出的子图是一个线性森林, 其中1≤α≤t, 则从E(G)到{1, 2, …, t}的一个映射φ称为t-线性染色。线性荫度la(G)表示图G的所有t-线性染色中最小的t。本文确定了最大度为Δ, 树宽最多为$\frac{\Delta+1}{4}$的图G, 其线性荫度$\operatorname{la}(G)=\left\lceil\frac{\Delta}{2}\right\rceil$。

关键词: 线性荫度, 线性染色, 树宽

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

中图分类号: 

  • 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] 杜红军,王慧娟. 不含相邻短圈的可嵌入图的线性荫度[J]. 《山东大学学报(理学版)》, 2023, 58(11): 147-154.
[2] 徐常青1,安丽莎1,杜亚涛2. 平面图线性2-荫度的一个上界[J]. 山东大学学报（理学版）, 2014, 49(04): 38-40.
[3] 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. J4, 2012, 47(6): 71-75.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 吴洪博,乔希民, . 命题逻辑系统Ｌn中公式相对于有限理论的∑Γ－模糊真度理论[J]. J4, 2008, 43(6): 1 -8 .
[2] 隋云云. 五值非线性序集逻辑系统中命题真度的分布[J]. J4, 2009, 44(1): 78 -82 .
[3] 吴鹏飞,孟祥增,刘俊晓,马凤娟 . 基于结构与内容的网页主题信息提取研究[J]. J4, 2006, 41(3): 131 -134 .
[4] 马新光. Dirichlet空间到Bloch空间的一个积分型算子[J]. J4, 2012, 47(4): 66 -69 .
[5] 严为绒, 洪宇, 朱珊珊, 车婷婷, 姚建民, 朱巧明. 基于语义场景的隐式篇章关系检测方法[J]. 山东大学学报（理学版）, 2014, 49(11): 59 -67 .
[6] 朱梦珺,蒋洪迅,许伟. 基于金融微博情感与传播效果的股票价格预测[J]. 山东大学学报（理学版）, 2016, 51(11): 13 -25 .
[7] 朱虹，张影. D(kS3)的不可约表示与Grothendieck群的环结构[J]. J4, 2009, 44(12): 17 -21 .
[8] . 基于移相法的三维面型测量系统优化算法研究[J]. J4, 2009, 44(6): 40 -45 .
[9] 胡丽霞,张建华. 三角代数上的零点Lie高阶可导映射[J]. J4, 2013, 48(4): 5 -9 .
[10] 李影, 宋卫东. 关于deSitter空间中的伪脐类时子流形[J]. 山东大学学报（理学版）, 2015, 50(10): 64 -67 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发