Operations Research Transactions >
2019 , Vol. 23 >Issue 1: 104 - 110
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.012
An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles
Received date: 2017-03-27
Online published: 2019-03-15
An edge-partition of a graph G is a decomposition of G into subgraphs G1, G2,…, Gm such that E(G)=E(G1)∪ E(G2)∪…∪ E(Gm) and E(Gi)∩ E(Gj)=∅ 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 lak(G) of a graph G is the least integer m such that G can be edge-partitioned into m linear k-forests. For extremities, la1(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 la2(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
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.012
[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.
/
| 〈 |
|
〉 |
