Article in volume
Authors:
Title:
The linear arboricity of graphs with low treewidth
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 475-487
Received: 2021-09-02 , Revised: 2022-04-20 , Accepted: 2022-04-20 , Available online: 2022-05-05 , https://doi.org/10.7151/dmgt.2456
Abstract:
Let $G$ be a graph with treewidth $k$. In the paper, it is proved that if
$k\leq 3$ and maximum degree $\Delta\geq 5$, or $k=4$ and $\Delta\geq 9$, or
$\Delta\geq 4k-3$ and $k\geq 5$, then the linear arboricity $la(G)$ of $G$ is
$\left\lceil\frac{\Delta}{2}\right\rceil$.
Keywords:
graph, minor, linear arboricity, linear forest, treewidth
References:
- J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III: Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.
- J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs IV: Linear arboricity, Networks 11 (1981) 69–72.
https://doi.org/10.1002/net.3230110108 - H.L. Bodlaender, A partial $k$-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998) 1–45.
https://doi.org/10.1016/S0304-3975(97)00228-4 - H.L. Bodlaender, Planar Graphs with Bounded Treewidth (Tech. Rep. RUU-CS-88-14, Dep. of Computer Science, Univ. of Utrecht, 1988).
- H. Bruhn, R. Lang and M. Stein, List edge-coloring and total coloring in graphs of low treewidth, J. Graph Theory 81 (2016) 272–282.
https://doi.org/10.1002/jgt.21874 - M. Cygan, J.-F. Hou, \L. Kowalik, B. Lužar and J.L. Wu, A planar linear arboricity conjecture, J. Graph Theory 69 (2012) 403–425.
https://doi.org/10.1002/jgt.20592 - R. Diestel, Graph Theory, 4th Edition (Springer-Verlag, New York, 2010).
- H. Enomoto and B. Péroche, The linear arboricity of some regular graphs, J. Graph Theory 8 (1984) 309–324.
https://doi.org/10.1002/jgt.3190080211 - F. Guldan, The linear arboricity of $10$ regular graphs, Math. Slovaca 36 (1986) 225–228.
- N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986) 309–322.
https://doi.org/10.1016/0196-6774(86)90023-4 - J.L. Wu, On the linear arboricity of planar graphs, J. Graph Theory 31 (1999) 129–134.
https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A - J.L. Wu, Y.W. Wu, The linear arboricity of planar graphs of maximum degree seven is four, J. Graph Theory 58 (2008) 210–220.
https://doi.org/10.1002/jgt.20305 - J.L. Wu, The linear arboricity of series-parallel graphs, Graphs Combin. 16 (2000) 367–372.
https://doi.org/10.1007/s373-000-8299-9 - J.L. Wu, Some path decompositions of Halin graphs, J. Shandong Min. Inst. 17 (1998) 92–96.
- J.L. Wu, F. Yang and H.M. Song, The linear arboricity of $K_{5}$-minor free graphs, submitted manuscript.
Close