THE LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITHOUT ADJACENT SHORT CYCLES
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let G be a planar graph with maximum degree Δ. The linear 2-arboricity $la_2$(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that (1) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+8$ if G has no adjacent 3-cycles; (2) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+10$ if G has no adjacent 4-cycles; (3) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+6$ if any 3-cycle is not adjacent to a 4-cycle of G.
Abstract
Let G be a planar graph with maximum degree Δ. The linear 2-arboricity $la_2$(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that (1) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+8$ if G has no adjacent 3-cycles; (2) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+10$ if G has no adjacent 4-cycles; (3) $la_2(G){\leq}{\lceil}\frac{\Delta}{2}\rceil+6$ if any 3-cycle is not adjacent to a 4-cycle of G.
참고문헌 (12)
- R. E. L. Aldred, "More on the linear k-arboricity of regular graphs", Australas. J. Combin, 18, pp.97~104 (1998)
- J. C. Bermond, "On linear k-arboricity", Discrete Math, 52(2), pp.123~132 (1984)
- G. J. Chang, "Algorithmic aspects of linear k-arboricity", Taiwanese J. Math, 3(1), pp.73~81 (1999)
- G. J. Chang, "Linear k-arboricity on trees", Discrete Appl. Math, 103(1), pp.281~287 (2000)
- B. L. Chen, "Decomposing graphs into forests of paths with size less than three", Australas. J. Combin, 3, pp.55~73 (1991)
- H. L. Fu, "The linear 2-arboricity of complete bipartite graphs", Ars Combin, 38, pp.309~318 (1994)
- M. Habib, "Some problems about linear arboricity", Discrete Math, 41(2), pp.219~220 (1982)
- B. Jackson, "On linear k-arboricity of cubic graphs", Discrete Math, 162(1), pp.293~297 (1996)
- K. W. Lih, "The linear 2-arboricity of planar graphs", Graphs Combin, 19(2), pp.241~248 (2003)
- Q. Ma, "Planar graphs without 5-cycles or without 6-cycles", Discrete Math (2008)[DOI]
- J. Qian, "The linear 2-arboricity of planar graphs without 4-cycles", J. Zhejiang Norm. Univ, 29(2), pp.121~125 (2006)
- C. Thomassen, "Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5", J. Combin. Theory Ser. B, 75(1), pp.100~109 (1999)