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

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

Abstract

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

CLC Number:

O157.5

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.

References

[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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	LIU Yao. On (1, 0)-relaxed strong edge-coloring of graphs [J]. Operations Research Transactions, 2021, 25(2): 115-126.
[2]	BAO Xiaoguang, LU Chao, HUANG Dongmei, YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[3]	CHEN Min, YANG Jianmin, ZHANG Hao, WANG Yiting. Weakly entire coloring of outerplanar graphs [J]. Operations Research Transactions, 2021, 25(1): 132-136.
[4]	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.
[5]	CHEN Tao. Upper bounds on minimum balanced bipartition of Hamilton plane graphs [J]. Operations Research Transactions, 2020, 24(3): 161-166.
[6]	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.
[7]	LV Xuezheng, WEI Erling, SONG Hongye. The basis number of join graphs [J]. Operations Research Transactions, 2018, 22(4): 148-152.
[8]	ZHANG Xin, LIU Weichan. The coloring of the class of 1-planar graphs and its subclasses [J]. Operations Research Transactions, 2017, 21(4): 135-152.
[9]	SU Zhenhua. The crossing number of the join product of C_6+3K_2 with P_n and C_n [J]. Operations Research Transactions, 2017, 21(3): 23-34.
[10]	ZHOU Zhidong, LI Long. On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n [J]. Operations Research Transactions, 2016, 20(4): 115-126.
[11]	SUN Lin, LUO Zhaoyang. Edge colourings of embedded special graphs [J]. Operations Research Transactions, 2015, 19(1): 125-130.
[12]	DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs [J]. Operations Research Transactions, 2014, 18(3): 116-120.
[13]	YU Guidong, ZHANG Chao, GONG Qijuan. Energy and Hamiltonicity of graphs [J]. Operations Research Transactions, 2014, 18(2): 40-48.
[14]	YE Yongsheng, LIU Fang, ZHAI Mingqing. Pebbling numbers of middle graphs of cycles and Graham's conjecture [J]. Operations Research Transactions, 2013, 17(3): 35-44.
[15]	WANG Guang-Hui, ZHOU Shan. Properly Colored Paths and Cycles in Complete Graphs [J]. Operations Research Transactions, 2011, 15(3): 51-56.