不含相交5-圈的平面图的线性2-荫度

doi:10.6040/j.issn.1671-9352.0.2019.095

摘要/Abstract

摘要： 设G是不含相交5-圈的平面图,证明了如果G是连通的并且δ(G)≥2,则G包含一条边xy,使得d(x)+d(y)≤10或者一个2-交错圈。由这个结果可以得到G的线性2-荫度la₂(G)≤「Δ/2+5,改进了不含5-圈的平面图的线性2-荫度的已知上界。

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

Abstract: Let G be a planar graph without intersecting 5-cycles. If G is connected and δ(G)≥2, then G contains an edge xy with d(x)+d(y)≤10 or a 2-alternating cycle is proved. By this result, its linear 2-arboricity la₂(G)≤「Δ/2+5 is obtained, which improves the known upper bound of la2(G) for planar graphs without 5-cycles.

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

中图分类号:

陈宏宇,钟斌. 不含相交5-圈的平面图的线性2-荫度[J]. 《山东大学学报(理学版)》, 2020, 55(7): 38-45.

CHEN Hong-yu, ZHONG Bin. Linear 2-arboricity of planar graphs without intersecting 5-cycles[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 38-45.

参考文献

[1] HABIB M, PÉRROCHE B. Some problems about linear arboricity[J]. Discrete Math, 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]. Australas J Combin, 1991, 3:55-73.
[3] FU H L, HUANG K C. The linear 2-arboricity of complete bipartite graphs.[J]. Australas J Combin, 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(1):100-109.
[5] CHANG G J, CHEN B L, FU H L, et al. Linear k-arboricities on trees[J]. Discrete Applied Mathematics, 2000, 103(1/2/3):281-287.
[6] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52(2):123-132.
[7] JACKSON B, WORMALD N C. On the linear k-arboricity of cubic graphs.[J]. Discrete Mathematics, 1996, 162(1/2/3):293-297.
[8] 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.
[9] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs and Combinatorics, 2003, 19:241-248.
[10] 钱景,王维凡. 不含4-圈的平面图的线性2-萌度[J]. 浙江师范大学学报(自然科学版)2006, 29(2): 121-125. QIAN Jing, WANG Weifan. The linear 2-arboricity of planar graphs without 4-cycles[J]. Journal of Zhejiang Normal University(Nat Sci), 2006, 29:121-125.
[11] MA Qin, WU Jianliang. Planar graphs without 5-cycles or without 6-cycles[J]. Discrete Mathematics, 2009, 309:2998-3005.
[12] CHEN Hongyu, TAN Xiang, WU Jianliang. The linear 2-arboricity of planar graphs without adjacent short cycles[J]. Bull Korean Math Soc, 2012, 49(1):145-154.
[13] 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-萌度[J].山东大学学报(理学版), 2012, 47(6): 71-75. WANG Ranqun, ZUO Liancui. The linear 2-arboricity of planar graphs without 4-cycles and 5-cycles[J]. Journal of Shandong University(Natural Science), 2012, 47(6): 71-75.
[14] 陈宏宇,张丽. 不含弦5-圈和弦6-圈的平面图的线性2-萌度[J]. 山东大学学报(理学版), 2014, 49(6):26-30. CHEN Hongyu, ZHANG Li. The linear 2-arboricity of planar graphs without 5-,6-cycles with chord[J]. Journal of Shandong University(Natural Science), 2014, 49(6): 26-30.
[15] NIU H X, CAI J S. Linear 2-Arboricity of planar graphs with neither 3-cycles nor adjacent 4-cycles[J]. Graphs and Combinatorics, 2013, 29(3):661-667.
[16] WANG W, LI Y, HU X, et al. Linear 2-arboricity of toroidal graphs[J/OL]. Bulletin of the Malaysian Mathematical Sciences Society, 2016. DOI: 10.1007/s40840-016-0434-z(2016).

相关文章 15

[1]	张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.
[2]	李强,马丽丽,王晓燕,吕莉娇. Hom-Jordan李代数的交换扩张[J]. 《山东大学学报(理学版)》, 2018, 53(12): 4-8.
[3]	陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22.
[4]	刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[5]	房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[6]	王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[7]	王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[8]	陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[9]	何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[10]	谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[11]	白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64.
[12]	朱海洋,顾毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[13]	孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129.
[14]	薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报（理学版）, 2015, 50(11): 60-66.
[15]	王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed