不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

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

运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 104-110.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.012

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

陈宏宇^1,*, 谭香²

1. 上海应用技术大学理学院, 上海 201418;
2. 山东财经大学数学与数量经济学院, 济南 250014

收稿日期:2017-03-27 出版日期:2019-03-15 发布日期:2019-03-15
通讯作者: 陈宏宇 E-mail:hongyuchen86@163.com
基金资助:
国家自然科学基金青年基金（No.11401386）

An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles

CHEN Hongyu^1,*, TAN Xiang²

1. School of Science, Shanghai Institute of Technology, Shanghai 201418, China;
2. School of Mathematics and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014, China

Received:2017-03-27 Online:2019-03-15 Published:2019-03-15

摘要/Abstract

摘要：

图G的一个边分解是指将G分解成子图G₁，G₂，…，G_m使得E（G）=E（G₁）∪ E（G₂）∪…∪ E（G_m），且对于i≠j，E（G_i）∩E（G_j）=∅.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k（G）是使得G可以边分解为m个线性k-森林的最小整数m.显然，la₁（G）是G的边色数χ'（G）；la_∞（G）表示每条分支路是无限长度时的情况，即通常所说的G的线性荫度la（G）.利用权转移的方法研究平面图的线性2-荫度la₂（G）.设G是不含有5-圈和相邻4-圈的平面图，证明了若G连通且δ（G）≥ 2，则G包含一条边xy使得d（x）+d（y）≤ 8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为?△/2?+4.

关键词: 平面图, 线性2-荫度, 圈

Abstract:

An edge-partition of a graph G is a decomposition of G into subgraphs G₁, G₂,…, G_m such that E(G)=E(G₁)∪ E(G₂)∪…∪ E(G_m) and E(G_i)∩ E(G_j)=∅ for i≠j. A linear k-forest is a graph in which each component is a path of length at most k. The linear k-arboricity la_k(G) of a graph G is the least integer m such that G can be edge-partitioned into m linear k-forests. For extremities, la₁(G) is the edge chromatic number χ'(G) of G; la_∞(G) representing the case when component paths have unlimited lengths is the ordinary linear arboricity la(G) of G. In this paper, we use the discharging method to study the linear 2-arboricity la₂(G) of planar graphs. Let G be a planar graph with neither 5-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge xy with d(x)+d(y) ≤ 8 or a 2-alternating cycle. By this result, we obtain the upper bound of the linear 2-arboricity of G is ?△/2?+4.

Key words: planar graph, linear 2-arboricity, cycle

中图分类号:

O157.5

陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.

CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles[J]. Operations Research Transactions, 2019, 23(1): 104-110.

参考文献

[1] Habib M, Péroche B. Some problems about linear arboricity[J]. Discrete Mathematics, 1982, 41:219-220.
[2] Chen B L, Fu H L, Huang K C. Decomposing graphs into forests of paths with size less than three[J]. Australasian Journal of Combinatorics, 1991, 3:55-73.
[3] Fu H L, Huang K C. The linear 2-arboricity of complete bipartite graphs[J]. Australasian Journal of Combinatorics, 1994, 38:309-318.
[4] Thomassen C. Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J]. Journal of Combinatorial Theory, Series B, 1999, 75:100-109.
[5] Chang G J. Algorithmic aspects of linear k-arboricity[J]. Taiwanese Journal of Mathematics, 1999, 3:73-81.
[6] Chang G J, Chen B L, Fu H L, et al. Linear k-arboricity on trees[J]. Discrete Applied Mathematics, 2000, 103:281-287.
[7] Bermond J C, Fouquet J L, Habib M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52:123-132.
[8] Jackson B, Wormald N C. On linear k-arboricity of cubic graphs[J]. Discrete Mathematics, 1996, 162:293-297.
[9] Aldred R E L, Wormald N C. More on the linear k-arboricity of regular graphs[J]. Australasian Journal of Combinatorics, 1998, 18:97-104.
[10] Lih K W, Tong L D, Wang W F. The linear 2-arboricity of planar graphs[J]. Graphs and Combinatorics, 2003, 19:241-248.
[11] Qian J, Wang W F. The linear 2-arboricity of planar graphs without 4-cycles[J]. Journal of Zhejiang Normal University, 2006, 29:121-125.
[12] Ma Q, Wu J L. Planar graphs without 5-cycles or without 6-cycles[J]. Discrete Mathematics, 2009, 309:2998-3005.
[13] Chen H Y, Tan X, Wu J L. The linear 2-arboricity of planar graphs without adjacent short cycles[J]. Bulletin of the Korean Mathematical Society, 2012, 49:145-154.
[14] 王苒群, 左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2012, 47(6):71-75.
[15] 陈宏宇, 张丽. 不含弦5-圈和弦6-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2014, 49(6):26-30.
[16] Niu H, Cai J. Linear 2-arboricity of planar graphs with neither 3-cycles nor adjacent 4-cycles[J]. Graphs and Combinatorics, 2013, 29:661-667.
[17] Zhang X, Liu G Z, Wu J L. On the linear arboricity of 1-planar graphs[J]. Operations Research Transactions, 2011, 15(3):38-44.

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles

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]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[6]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[7]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[8]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[9]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[10]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[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.