The linear 2-arboricity of planar graphs without adjacent short cycles
Bull. Korean Math. Soc. 2012 Vol. 49, No. 1, 145-154
https://doi.org/10.4134/BKMS.2012.49.1.145
Published online January 1, 2012
Hong-Yu Chen, Xiang Tan, and Jian-Liang Wu
Shanghai Institute of Technology, Shandong University of Finance, Shandong University
Abstract : Let $G$ be a planar graph with maximum degree $\Delta$. 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$.
Keywords : planar graph, linear 2-arboricity, cycle
MSC numbers : 05C15
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd