1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Linear Arboricity of Graphs with Low Treewidth

Published Online: 27 May 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 02 Sep 2021
Accepted: 20 Apr 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 \left\lceil {{\Delta \over 2}} \right\rceil

Keywords

MSC 2010

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

[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.323011010810.1002/net.3230110108 Search in Google Scholar

[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-410.1016/S0304-3975(97)00228-4 Search in Google Scholar

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

[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.2187410.1002/jgt.21874 Search in Google Scholar

[6] M. Cygan, J.-F. Hou, Ł. 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.2059210.1002/jgt.20592 Search in Google Scholar

[7] R. Diestel, Graph Theory, 4th Edition (Springer-Verlag, New York, 2010).10.1007/978-3-642-14279-6 Search in Google Scholar

[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.319008021110.1002/jgt.3190080211 Search in Google Scholar

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

[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-410.1016/0196-6774(86)90023-4 Search in Google Scholar

[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:2¡129::AID-JGT5¿3.0.CO;2-A Search in Google Scholar

[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.2030510.1002/jgt.20305 Search in Google Scholar

[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-910.1007/s373-000-8299-9 Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo