最大度大于等于7的平面图的线性荫度

doi:10.15960/j.cnki.issn.1007-6093.2020.03.012

运筹学学报 ›› 2020, Vol. 24 ›› Issue (3): 154-160.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.012

最大度大于等于7的平面图的线性荫度

陈洪玲¹, 王慧娟^2,*, 孙凤艳¹, 薛娟¹, 高红伟¹

青岛大学数学与统计学院, 山东青岛 266071

收稿日期:2017-11-20 发布日期:2020-09-05
通讯作者: 王慧娟 E-mail:sduwhj@163.com
基金资助:
国家自然基金（Nos.71571108，11501316），国家自然科学基金国际（地区）合作交流项目（Nos.71611530712，61661136002）

Linear arboricity of planar graphs with maximum degree at least seven

CHEN Hongling¹, WANG Huijuan^2,*, SUN Fengyan¹, XUE Juan¹, GAO Hongwei¹

School of Mathematics and Statistics, Qingdao University, Qingdao 266071, Shandong, China

Received:2017-11-20 Published:2020-09-05

摘要/Abstract

摘要： 图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度，它是一种非正常的边染色，即在简单无向图中，它的边可以分割成线性森林的最小数量。研究最大度$\bigtriangleup（G）\geq7$的平面图$G$的线性荫度，证明了对于两个固定的整数$i$，$j\in\{5，6，7\}$，如果图$G$中不存在相邻的含弦$i$，$j$-圈，则图$G$的线性荫度为$\lceil\frac\bigtriangleup2\rceil$。

关键词: 平面图, 线性森林, 圈

Abstract: Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transferring in a computer network, computation of Hessians matrix and so on. There is an important coloring in the coloring of the graph, linear arboricity, which is an improper edge coloring, and the linear arboricity of an undirected graph is the smallest number of linear forests whose edges can be partitioned into. In this paper, we mainly studied linear arboricity on planar graphs with maximum degree $\bigtriangleup\geq7$ and we have proved that for the two fixed integers $i$, $j\in \{5, 6, 7\}$, if there is no adjacent chordal $i$, $j$-cycles, then the linear arboricity of $G$ is $\lceil\frac\bigtriangleup2\rceil$.}

Key words: planar graph, linear forest, cycle

中图分类号:

O157.5

陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.

CHEN Hongling, WANG Huijuan, SUN Fengyan, XUE Juan, GAO Hongwei. Linear arboricity of planar graphs with maximum degree at least seven[J]. Operations Research Transactions, 2020, 24(3): 154-160.

参考文献

[1] Harary F. Covering and packing in graphs I[J]. Annals of the New York Academy of Sciences,1970, 175:198-205.
[2] Akiyama J, Exoo G, Harary Frank. Covering and packing in graphs Ⅲ:cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(5):405-417.
[3] Jin Akiyama, Geoffrey Exoo, Frank Harary. Covering and packing in graphs IV:Linear arboricity[J]. Networks, 1981, 11:69-72.
[4] Enomoto Hikoe, PWroche Bernard. The linear arboricity of some regular graphs[J]. Graph Theory, 1984, 8:309-324.
[5] Filip Guldan. The linear arboricity of 10 regular graphs[J]. Mathematica Slovaca, 1986, 36:225-228.
[6] Wu J L. Some path decompositions of Halin graphs[J]. Shandong Mining Institute, 1996, 15:219-222.
[7] Wu J L. The linear arboricity of series-parallel graphs[J]. Graphs & Combinatorics, 2000, 16(3):367-372.
[8] Péroche Bernard. Complexity of the linear arboricity of a graph[J]. RAIRO-Operations Research, 1982, 16:125-129.
[9] Alon Noga. The linear arboricity of graphs[J]. Israel Journal of Mathematics,1988, 62(3):311-325.
[10] Alon Noga, Teague V J, Wormald N C. Linear arboricity and linear k-arboricity of regular graphs[J]. Graphs and Combinatorics, 2001, 17:11-16.
[11] AÏt-djafer Houria. Linear arboricity for graphs with multiple edges[J]. Graph Theory, 1987, 11:135-140.
[12] McDiarmid C J H, Reed B A. The linear arboricity of some regular graphs[J]. Random Structure Algorithms, 1990, 1:433-445.
[13] Wu J L. On the linear arboricity of planar graphs[J]. Graph Theory,1999, 31:129-134.
[14] Wu J L, Wu Y W. The linear arboricity of planar graphs of maximum degree seven are four[J]. Graph Theory, 2008, 58:210-220.
[15] Cygan M, Hou J F, Kowalik L, et al. A planar linear arboricity conjecture[J]. Graph Theory, 2012, 69:403-425.
[16] Wang H J, Wu L D, Wu W L, et al. Minimum number of disjoint linear forests covering a planar graph[J]. Journal of Combinatorial Optimization, 2014, 28:274-287.
[17] Wu J L, Hou J F, Sun X Y. A note on the linear arboricity of planar graphs without 4-cycles[J]. ISO-RA, 2009, 09:174-178.

最大度大于等于7的平面图的线性荫度

Linear arboricity of planar graphs with maximum degree at least seven

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[2]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[3]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[4]	余桂东, 阮征, 舒阿秀, 于涛. 单圈图的次大(拉普拉斯)分离度[J]. 运筹学学报, 2020, 24(4): 128-134.
[5]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[6]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[7]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[8]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[9]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[10]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.
[11]	丁超, 余桂东. 含偶圈图的Laplacian 谱刻画[J]. 运筹学学报, 2018, 22(4): 135-140.
[12]	吕雪征, 魏二玲, 宋宏业. 联图的圈基[J]. 运筹学学报, 2018, 22(4): 148-152.
[13]	秦倩楠, 邵燕灵. 三圈图的极小广义和连通指数[J]. 运筹学学报, 2018, 22(1): 142-150.
[14]	张欣, 刘维婵. 1-平面图及其子类的染色[J]. 运筹学学报, 2017, 21(4): 135-152.
[15]	苏振华. 六阶图C_6+3K_2与P_n, C_n的联图交叉数[J]. 运筹学学报, 2017, 21(3): 23-34.