| Citation: |
Xiaoxue Hu, Juan Liu, Yiqiao Wang. AN IMPROVED UPPER BOUND ON THE LINEAR 2-ARBORICITY OF TOROIDAL GRAPHS[J]. Journal of Applied Analysis & Computation, 2022, 12(4): 1672-1678. doi: 10.11948/20220107
|
AN IMPROVED UPPER BOUND ON THE LINEAR 2-ARBORICITY OF TOROIDAL GRAPHS
-
Abstract
The linear $ 2 $-arboricity $ {\rm la}_2(G) $ of a graph $ G $ is the smallest integer $ k $ such that $ G $ can be partitioned into $ k $ edge-disjoint forests, whose components are paths of length at most 2. In this paper, we prove that every toroidal graph $ G $ has la$ _{2}(G)\leq \big\lceil\frac{\Delta(G)+1}{2}\big\rceil + 6 $. Since $ K_7 $ is a toroidal graph with la$ _2(K_7)=6=\big\lceil\frac{\Delta(K_7)+1}{2}\big\rceil + 2 $, our solution is within four from optimal.
-
Keywords:
- Toroidal graph /
- linear 2-arboricity /
- maximum degree /
- edge-partition
-
-
References
[1] M. Basavaraju, A. Bishnu, M. Francis and D. Pattanayak, The Linear Arboricity Conjecture for 3-Degenerate Graphs, In: I. Adler, H. Mš¹ller (eds) Graph-Theoretic Concepts in Computer Science. WG 2020. Lecture Notes in Computer Science, vol 12301. Springer, Cham. DOI: 10.1007/978-3-030-604400_30. [2] J. C. Bermond, J. L. Fouquet, M. Habib and B. Péroche, On linear k-arboricity, Discrete Math., 1984, 52(2-3), 123-132. doi: 10.1016/0012-365X(84)90075-X [3] B. Chen, H. Fu and K. Huang, Decomposing graphs into forests of paths with size less than three, Australas. J. Combin., 1991, 3, 55-73. [4] A. Ferber, J. Fox and V. Jain, Towards the linear arboricity conjecture, J. Combin. Theory Ser. B, 2020, 142, 56-79. doi: 10.1016/j.jctb.2019.08.009 [5] M. Habib and B. Péroche, Some problems about linear arboricity, Discrete Math., 1982, 41(2), 219-220. doi: 10.1016/0012-365X(82)90209-6 [6] R. Kim and L. Postle, The list linear arboricity of graphs, J. Graph Theory, 2021, 98(1), 125-140. doi: 10.1002/jgt.22685 [7] K. W. Lih, L. Tong and W. Wang, The linear 2-arboricity of planar graphs, Graphs Combin., 2003, 19(2), 241-248. doi: 10.1007/s00373-002-0504-x [8] J. Liu, X. Hu, W. Wang and Y. 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 [9] J. Liu, Y. Wang, P. Wang, L. Zhang and W. Wang, An improved upper Bound on the linear 2-arboricity of 1-planar graphs, Acta Math. Sin. (Engl. Ser. ), 2021, 37(2), 262-278. doi: 10.1007/s10114-020-9488-9 [10] Q. Ma, J. Wu and X. Yu, Planar graphs without 5-cycles or without 6-cycles, Discrete Math., 2009, 309(10), 2998-3005. doi: 10.1016/j.disc.2008.07.033 [11] W. Wang, Y. Li, X. Hu and Y. Wang, Linear 2-arboricity of toroidal graphs, Bull. Malays. Math. Sci. Soc., 2018, 41(4), 1907-1921. doi: 10.1007/s40840-016-0434-z [12] Y. Wang, An improved upper bound on the linear 2-arboricity of planar graphs, Discrete Math., 2016, 339(1), 39-45. doi: 10.1016/j.disc.2015.07.003 [13] Y. Wang, X. Hu and W. Wang, A note on the linear 2-arboricity of planar graphs, Discrete Math., 2017, 340(7), 1449-1455. doi: 10.1016/j.disc.2017.01.027 -
-
Export File
Citation
Xiaoxue Hu, Juan Liu, Yiqiao Wang. AN IMPROVED UPPER BOUND ON THE LINEAR 2-ARBORICITY OF TOROIDAL GRAPHS[J]. Journal of Applied Analysis & Computation, 2022, 12(4): 1672-1678. doi: 10.11948/20220107
DownLoad: