6-圈至多含一弦平面图的线性荫度

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

运筹学学报 ›› 2019, Vol. 23 ›› Issue (2): 113-119.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.011

6-圈至多含一弦平面图的线性荫度

罗朝阳^*, 孙林

昌吉学院数学系, 新疆昌吉 831100

收稿日期:2017-03-09 出版日期:2019-06-15 发布日期:2019-06-15
通讯作者: 罗朝阳 E-mail:sdmlzy@163.com
基金资助:
新疆维吾尔自治区自然科学基金（Nos.2016D01C005，2016D01C012），新疆高校科研计划重点项目（No.XJEDU2014I046）

The linear aboricity of planar graphs with 6-cycles containing at most one chord

LUO Zhaoyang^*, SUN Lin

Department of Mathematics, Changji University, Changji 831100, Xinjiang, China

Received:2017-03-09 Online:2019-06-15 Published:2019-06-15

摘要/Abstract

摘要： 线性森林是指每个连通分支都是路的图.图G的线性荫度la（G）等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了，若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图，则la（G）=「△（G）/2」.

关键词: 圈, 平面图, 线性荫度, 权转移方法

Abstract: The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, using the discharging method, it is proved that for a planar graph G, la(G)=「△(G)/2」 if △(G) > 7 and every 6-cycle of G contains at most one chord.

Key words: cycle, planar graph, linear arboricity, discharging method

中图分类号:

O157.5

罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.

LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord[J]. Operations Research Transactions, 2019, 23(2): 113-119.

参考文献 20

[1]	Bondy J A, Murty U S R. Graphs Theory with Applications[M]. London:Macmillan Press Ltd, 1979.
[2]	Akiyama J, Exoo G, Harary F. Covering and packing in graphs Ⅲ:cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30:405-417.
[3]	Péroche B. Complexity of the linear arboricity of a graph[J]. RAIRO Operations Research, 1982, 16:125-129.
[4]	Enomoto H, Péroche B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 1984, 8:309-324.
[5]	Guldan F. The linear arboricity of 10-regular graphs[J]. Mathematica Slovaca, 1986, 36:225- 228.
[6]	Guldan F. Some results on linear arboricity[J]. Journal of Graph Theory, 1986, 10:505-509.
[7]	Wu J L. The linear arboricity of series-parallel graphs[J]. Graphs and Combinatorics, 2000, 16:367-372.
[8]	Wu J L, Liu G Z, Wu Y L. The linear arboricity of composition graphs[J]. Journal of Systems Science and Complexity, 2002, 15:372-375.
[9]	Harary F. Covering and packing in graphs I[J]. Annals New York Academy of Sciences, 1970, 175:198-205.
[10]	Wu J L, Hou J F, Sun X Y. A note on the linear arboricity of planar graphs without 4- cycles[C]//The Eighth International Symposium on Operations Research and Its Applications (ISORA.09), Zhangjiajie:Hunan University, 2009:174-178.
[11]	Chen H Y, Qi J M. The linear arboricity of planar graphs with maximum degree at least 5[J]. Information Processing Letters, 2012, 112:767-771.
[12]	Cygan M, Hou J F, Kowalik L, et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2012, 60:403-425.
[13]	Tan X, Chen H Y, Wu J L. The linear arboricity of planar graphs with maximum degree at least five[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2011, 34:541-552.
[14]	Tan X, Chen H Y, Wu J L. The linear arboricity of planar graphs without 5-cycles and 6-cycles[J]. Ars Combinatoria, 2010, 97A:367-375.
[15]	Wu J L. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31:129-134.
[16]	Wu J L, Wu Y W. The linear arboricity of planar graphs of maximum degree seven is four[J]. Journal of Graph Theory, 2008, 58:210-220.
[17]	Wu J L, Hou J F, Liu G Z. The linear of planar graphs with no short cycles[J]. Theoretical Computer Science, 2007, 381:230-233.
[18]	Wang H J, Liu B, Wu J L. The linear arboricity of planar graphs without chordal short cycles[J]. Utilitas Mathematica, 2012, 87:255-263.
[19]	Chen H Y, Tan X, Wu J L, et al. The linear arboricity of planar graphs without 5-, 6-cycles with chords[J]. Graphs and Combinatorics, 2013, 29:373-385.
[20]	Chen X L, Wu J L. The linear arboricity of planar graphs without 5-cycles with two chords[J]. Filomat, 2016, 30:1134-1142.

6-圈至多含一弦平面图的线性荫度

The linear aboricity of planar graphs with 6-cycles containing at most one chord

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 20

相关文章 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]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[6]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[7]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[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.