Geodesic
The linear arboricity of graphs with low treewidth
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 475-487 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G be a graph with treewidth k. In the paper, it is proved that if k≤ 3 and maximum degree Δ≥ 5, or k=4 and Δ≥ 9, or Δ≥ 4k-3 and k≥ 5, then the linear arboricity la(G) of G is ⌈Δ2⌉.
Keywords: graph, minor, linear arboricity, linear forest, treewidth 
@article{DMGT_2024_44_2_a3,
     author = {Tan, Xiang and Wu, Jian-Liang},
     title = {The linear arboricity of graphs with low treewidth},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {475--487},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a3/}
}
TY  - JOUR
AU  - Tan, Xiang
AU  - Wu, Jian-Liang
TI  - The linear arboricity of graphs with low treewidth
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 475
EP  - 487
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a3/
LA  - en
ID  - DMGT_2024_44_2_a3
ER  - 
%0 Journal Article
%A Tan, Xiang
%A Wu, Jian-Liang
%T The linear arboricity of graphs with low treewidth
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 475-487
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a3/
%G en
%F DMGT_2024_44_2_a3
Tan, Xiang; Wu, Jian-Liang. The linear arboricity of graphs with low treewidth. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 475-487. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a3/

[1] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III:} Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.

[2] 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

[3] 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

[4] H.L. Bodlaender, Planar Graphs with Bounded Treewidth (Tech. Rep. RUU-CS-88-14, Dep. of Computer Science, Univ. of Utrecht, 1988).

[5] 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

[6] 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

[7] R. Diestel, Graph Theory, 4th Edition (Springer-Verlag, New York, 2010).

[8] 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

[9] F. Guldan, The linear arboricity of 10 regular graphs, Math. Slovaca 36 (1986) 225–228.

[10] 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

[11] 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:23.0.CO;2-A

[12] 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

[13] 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

[14] J.L. Wu, Some path decompositions of Halin graphs, J. Shandong Min. Inst. 17 (1998) 92–96.

[15] J.L. Wu, F. Yang and H.M. Song, The linear arboricity of K5-minor free graphs, submitted manuscript.