DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

X. Tan

Xiang Tan

Shandong University of Finance and Economics

email: xtandw@126.com

J.-L. Wu

Jian-Liang Wu

School of MathematicsShandong UniversityJinanShandong250100 P.R. CHINA

email: jlwu@sdu.edu.cn

Title:

The linear arboricity of graphs with low treewidth

PDF

Source:

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:

  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:2<129::AID-JGT5>3.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 $K_{5}$-minor free graphs, submitted manuscript.
Close