LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITH MAXIMUM DEGREE NINE

Xiaoxue Hu; Jiangxu Kong; Yiqiao Wang

doi:10.11948/20200448

2021 Volume 11 Issue 4

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2021 > 11(4): 2193-2210

Next Article Previous Article

Xiaoxue Hu, Jiangxu Kong, Yiqiao Wang. LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITH MAXIMUM DEGREE NINE[J]. Journal of Applied Analysis & Computation, 2021, 11(4): 2193-2210. doi: 10.11948/20200448

Citation:

Xiaoxue Hu, Jiangxu Kong, Yiqiao Wang. LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITH MAXIMUM DEGREE NINE[J]. Journal of Applied Analysis & Computation, 2021, 11(4): 2193-2210. doi: 10.11948/20200448

LINEAR 2-ARBORICITY OF PLANAR GRAPHS WITH MAXIMUM DEGREE NINE

1.
School of Science, Zhejiang University of Science & Technology, 310023 Hangzhou, China
2.
School of Science, China Jiliang University, 310018 Hangzhou, China
3.
School of Management, Beijing University of Chinese Medicine, 100029 Beijing, China

Corresponding author: Email: yqwang@bucn.edu.cn(Y. Wang)
Fund Project: The authors were supported by National Science Foundation of China (11801512, 11901525, 11701541, 12071048)

Abstract

Abstract

The linear 2-arboricity la$_2(G)$ of a graph $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 show that every planar graph $G$ with maximum degree $\Delta=9$ has la$_2(G)\le 8$, which extends a known result that every planar graph $G$ with $\Delta\ge10$ has la$_2(G)\le \Delta-1$.
- Plane graph /
- linear 2-arboricity /
- maximum degree
MSC: 05C15

FullText(HTML)

References

[1]	R. E. L. Aldred and N. C. Wormald, More on the linear k-arboricity of regular graphs, Australas. J. Combin., 1998, 18, 97-104. Google Scholar
[2]	J. C. Bermond, J. L. Fouquet, M. Habib and B. Peroche, On linear k-arboricity, Discrete Math., 1984, 52, 123-132. doi: 10.1016/0012-365X(84)90075-X CrossRef Google Scholar
[3]	G. J. Chang, B. L. Chen, H. L. Fu and K. C. Huang, Linear k-arboricities on trees, Discrete Appl. Math., 2000, 103, 281-287. doi: 10.1016/S0166-218X(99)00247-4 CrossRef Google Scholar
[4]	B. L. Chen and K. C. Huang, On the linear k-arboricity of K_n and K_{n, n}, Discrete Math., 2002, 254, 51-61. doi: 10.1016/S0012-365X(01)00365-X CrossRef Google Scholar
[5]	B. L. Chen, H. L. Fu and K. C. Huang, Decomposing graphs into forests of paths with size less than three, Australas. J. Combin., 1991, 3, 55-73. Google Scholar
[6]	M. Habib and B. Peroche, Some problems about linear arboricity, Discrete Math., 1982, 41, 219-220. doi: 10.1016/0012-365X(82)90209-6 CrossRef Google Scholar
[7]	B. Jackson and N. C. Wormald, On the linear k-arboricity of cubic graphs, Discrete Math., 1996, 162, 293-297. doi: 10.1016/0012-365X(95)00293-6 CrossRef Google Scholar
[8]	K. W. Lih, L. D. Tong and W. F. Wang, The linear 2-arboricity of planar graphs, Graphs & Combin., 2003, 19, 241-248. Google Scholar
[9]	K. W. Lih, L. D. Tong and W. F. Wang, The linear 2-arboricity of outerplanar graphs, Ars Combin., 2004, 73, 13-22. Google Scholar
[10]	J. Liu, X. X. Hu, W. F. Wang and Y. Q. Wang, Light structures in 1-planar graphs with an application to linear 2-arboricity, Discrete Appl. Math., 2019, 267, 120-130. doi: 10.1016/j.dam.2019.05.001 CrossRef Google Scholar
[11]	Q. Ma, J. L. Wu and X. Yu, Planar graphs without 5-cycles or without 6-cycles, Discrete Math., 2009, 309, 2998-3005. doi: 10.1016/j.disc.2008.07.033 CrossRef Google Scholar
[12]	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, 1999, 75, 100-109. doi: 10.1006/jctb.1998.1868 CrossRef Google Scholar
[13]	V. G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz., 1965, 5, 9-17. Google Scholar
[14]	W. F. Wang, Y. C. Li, X. X. Hu and Y. Q. Wang, Linear 2-arboricity of toroidal graphs, Bull. Malays. Math. Sci. Soc., 2018, 41, 1907-1921. doi: 10.1007/s40840-016-0434-z CrossRef Google Scholar
[15]	Y. Q. Wang, An improved upper bound on the linear 2-arboricity of planar graphs, Discrete Math., 2016, 339, 39-45. doi: 10.1016/j.disc.2015.07.003 CrossRef Google Scholar
[16]	Y. Q. Wang, X. X. Hu and W. F. Wang, A note on the linear 2-arboricity of planar graphs, Discrete Math., 2017, 340, 1449-1455. doi: 10.1016/j.disc.2017.01.027 CrossRef Google Scholar