Linear \(k\)-arboricities on trees. (English) Zbl 0958.05069
Authors’ summary: For a fixed positive integer \(k\), the linear \(k\)-arboricity \(\text{la}_k(G)\) of a graph \(G\) is the minimum number \(\ell\) such that the edge set \(E(G)\) can be partitioned into \(\ell\) disjoint sets and that each induces a subgraph whose components are paths of length at most \(k\). This paper studies linear \(k\)-arboricity from an algorithm point of view. In particular, we present a linear-time algorithm to determine whether a tree \(T\) has \(\text{la}_k(T)\leq m\).
Reviewer: C.Lai (Zhangzhou)
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C05 | Trees |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Ait-Djafter, H., Linear arboricity for graphs with maximum degree six or seven and edge multiplicity two, Ars. Combin., 20, 5-16 (1985) · Zbl 0595.05021 |
| [2] | Akiyama, J., Three developing topics in graph theory, Doctoral Dissertation (1980), University of Tokyo |
| [3] | J. Akiyama, A status on the linear arboricity, Lecture Notes in Computer Science, Vol. 108, Springer, Berlin, 1981, 38-44.; J. Akiyama, A status on the linear arboricity, Lecture Notes in Computer Science, Vol. 108, Springer, Berlin, 1981, 38-44. · Zbl 0456.68072 |
| [4] | Akiyama, J.; Chvátal, V., A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts and Sci., NMS, 2, 1-3 (1981) |
| [5] | Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs III, cyclic and acyclic invariants, Math. Slovaca, 30, 405-417 (1980) · Zbl 0458.05050 |
| [6] | Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs IV, linear arboricity, Networks, 11, 69-72 (1981) · Zbl 0479.05027 |
| [7] | Akiyama, J.; Kano, M., Path factors of a graph, Graph Theory and its Applications (1984), Wiley: Wiley New York |
| [8] | Alon, N., The linear arboricity of graphs, Israel J. Math., 62, 311-325 (1988) · Zbl 0673.05019 |
| [9] | Bermond, J. C.; Fouquet, J. L.; Habib, M.; Peroche, B., On linear \(k\)-arboricity, Discrete Math., 52, 123-132 (1984) · Zbl 0556.05054 |
| [10] | Chang, G. J., Algorithmic aspects of linear \(k\)-arboricity, Taiwanese J. Math., 3, 73-81 (1999) · Zbl 0927.05073 |
| [11] | C.Y. Chen, Y.P. Chen, G.J. Chang, The tree arboricity of a graph, submitted for publication.; C.Y. Chen, Y.P. Chen, G.J. Chang, The tree arboricity of a graph, submitted for publication. |
| [12] | Chen, B. L.; Fu, H. L.; Huang, K. C., Decomposing graphs into forests of paths with size less than three, Austr. J. Combin., 3, 55-73 (1991) · Zbl 0758.05074 |
| [13] | B.L. Chen, K.C. Huang, On the linear \(kK_nK_{nn\) |
| [14] | Enomoto, H., The linear arboricity of 5-regular graphs. The linear arboricity of 5-regular graphs, Technical Report, Dept. of Information Sci. (1981), Univ. of Tokyo |
| [15] | Enomoto, H.; Peroche, B., The linear arboricity of some regular graphs, J. Graph Theory, 8, 309-324 (1984) · Zbl 0581.05017 |
| [16] | Fu, H. L.; Huang, K. C., The linear 2-arboricity of complete bipartite graphs, Ars. Combinatoria, 38, 309-318 (1994) · Zbl 0814.05061 |
| [17] | Guldan, F., The linear arboricity of 10-regular graphs, Math. Slovaca, 36, 225-228 (1986) · Zbl 0612.05050 |
| [18] | Guldan, F., Some results on linear arboricity, J. Graph Theory, 10, 505-509 (1986) · Zbl 0651.05029 |
| [19] | Habib, M.; Peroche, P., Some problems about linear arboricity, Discrete Math., 41, 219-220 (1982) · Zbl 0486.05053 |
| [20] | Habib, M.; Peroche, P., \(La k\)-arboricité linéaire des arbres, Ann. Discrete Math., 17, 307-317 (1983) · Zbl 0523.05025 |
| [21] | Harary, F., Covering and packing in graphs I, Ann. New York Acad. Sci., 175, 198-205 (1970) · Zbl 0226.05119 |
| [22] | Holyer, I., The NP-completeness of edge colourings, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034 |
| [23] | K.C. Huang, Some results on linear \(k\); K.C. Huang, Some results on linear \(k\) |
| [24] | F. Jaeger, Etude de quelques invariants et problèmes d’existence en théorie des graphes, Thèse d’Etat, IMAG Grenbole, 1976.; F. Jaeger, Etude de quelques invariants et problèmes d’existence en théorie des graphes, Thèse d’Etat, IMAG Grenbole, 1976. |
| [25] | Nakayama, A.; Peroche, B., Linear arboricity of digraphs, Networks, 17, 39-53 (1987) · Zbl 0649.05029 |
| [26] | Peroche, B., Complexité de l’arboricité lináire d’un graphe, RAIRO, 16 (1982) · Zbl 0492.05025 |
| [27] | Tomasta, P., Note on linear arboricity, Math. Slovaca, 32, 239-242 (1982) · Zbl 0494.05047 |
| [28] | Yeh, H. G.; Chang, G. J., The path-partition problem in bipartite distance-hereditary graphs, Taiwanese J. Math., 2, 353-360 (1998) · Zbl 0917.05069 |
| [29] | Yeh, T. W., Linear arboricities of complete \(r\)-partite graphs. Linear arboricities of complete \(r\)-partite graphs, Master Thesis, Dept. Applied Math. (June 1997), National Chiao Tung Univ: National Chiao Tung Univ Hsinchu, Taiwan |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
