Abstract
Let G be a planar graph with neither 3-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge uv with d(u) + d(v) ≤ 7 or a 2-alternating cycle. By this result, we obtain that G’s linear 2-arboricity \({la_{2}(G)\leq\lceil\frac{\Delta(G)+1}{2}\rceil+4.}\).
Similar content being viewed by others
References
Akiyama, J. Three developing topics in graph theory. Doctoral dissertation, University of Tokyo (1980)
Akiyama J., Exoo G., Harary F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405–417 (1980)
Aldred R.E.L., Wormald N.C.: More on the linear k-arboricity of regular graphs. Aust. J. Comb. 18, 97–104 (1998)
Bermond J.C., Fouquet J.L., Habib M., Péroche B.: On linear k-arboricity. Discret. Math. 52, 123–132 (1984)
Chang G.J.: Algorithmic aspects of linear k-arboricity. Taiwan. J. Math. 3, 73–81 (1999)
Chang G.J., Chen B.L., Fu H.L., Huang K.C.: Linear k-arboricities on trees. Discret. Appl. Math. 103, 281–287 (2000)
Chen B.L., Fu H.L., Huang K.C.: Decomposing graphs into forests of paths with size less than three. Aust. J. Comb 3, 55–73 (1991)
Enomoto H., Péroche B.: The linear arboricity of some regular graphs. J. Graph Theory 8, 309–324 (1984)
Fu H.L., Huang K.C.: The linear 2-arboricity of complete bipartite graphs. Ars Comb. 38, 309–318 (1994)
Guldan F.: The linear arboricity of 10-regular graphs. Math. Slovaca 36, 225–228 (1986)
Habib M., Péroche P.: Some problems about linear arboricity. Discret. Math. 41, 219–220 (1982)
Jackson B., Wormald N.C.: On linear k-arboricity of cubic graphs. Discret. Math. 162, 293–297 (1996)
Lih K.W., Tong L.D., Wang W.F.: The linear 2-arboricity of planar graphs. Graphs Comb. 19, 241–248 (2003)
Ma Q., Wu J.L., Yu X.: Planar graphs without 5-cycles or without 6-cycles. Discret. Math. 309, 2998–3005 (2009)
Qian J., Wang W.F.: The linear 2-arboricity of planar graphs without 4-cycles. J.Zhejiang Norm. Univ. 29, 121–125 (2006)
Thomassen C.: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. J. Comb. Theory Ser. B 75, 100–109 (1999)
Wu J.L.: On the linear arboricity of planar graphs. J. Graph Theory 31, 129–134 (1999)
Wu J.L.: The linear arboricity of series-parallel graphs. Graph Comb. 16, 367–372 (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by a research grant Natural Science Foundation of Shandong Province (ZR2009AM009).
Rights and permissions
About this article
Cite this article
Niu, HX., Cai, JS. Linear 2-Arboricity of Planar Graphs with Neither 3-Cycles Nor Adjacent 4-Cycles. Graphs and Combinatorics 29, 661–667 (2013). https://doi.org/10.1007/s00373-011-1122-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1122-2