zbMATH — the first resource for mathematics

The linear arboricity of graphs. (English) Zbl 0673.05019
Summary: A linear forest is a forest in which each connected component is a path. The linear arboricity \(\ell a(G)\) of a graph G is the minimum number of linear forests whose union is the set of all edges of G. The linear arboricity conjecture asserts that for every simple graph G with maximum degree \(\Delta =\Delta (G)\), \[ \ell a(G)\leq \lceil (\Delta +1)/2\rceil. \] Although this conjecture received a considerable amount of attention, it has been proved only for \(\Delta\leq 6\), \(\Delta =8\) and \(\Delta =10\), and the best known general upper bound for \(\ell a(G)\) is \(\ell a(G)\leq \lceil 3\Delta /5\rceil\) for even \(\Delta\) and \(\ell a(G)\leq \lceil (3\Delta +2)/5\rceil\) for odd \(\Delta\). Here we prove that for every \(\epsilon >0\) there is a \(\Delta_ 0=\Delta_ 0(\epsilon)\) so that \(\ell a(G)\leq (+\epsilon)\Delta\) for every G with maximum degree \(\Delta \geq \Delta_ 0\). To do this, we first prove the conjecture for every G with an even maximum degree \(\Delta\) and with girth \(g\geq 50\Delta\).

05C05 Trees
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] J. Akiyama,A status on the linear arboricity, Lecture Notes in Comp. Science108, New York, 1981, pp. 38–44.
[2] I. Algor and N. Alon,The star arboricity of graphs, in preparation. · Zbl 0684.05033
[3] J. Akiyama and V. Chvátal,A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts & Sci., NMS No. 2 (1981), 1–3.
[4] H. Ait-Djafter,Linear arboricity for graphs with maximum degree six or seven and edgemultiplicity two, Ars Combinatoria20 (1985), 5–16.
[5] J. Akiyama, G. Exoo and F. Harary,Covering and packing in graphs III. Cyclic and acyclic invariants, Math. Slovaca30 (1980), 405–417. · Zbl 0458.05050
[6] J. Akiyama, G. Exoo and F. Harary,Covering and packing in graphs IV. Linear arboricity, Networks11 (1981), 69–72. · Zbl 0479.05027 · doi:10.1002/net.3230110108
[7] J. Akiyama and M. Kano,Path factors of a graph, in:Graph Theory and its Applications, Wiley and Sons, New York, 1984.
[8] Y. Aoki,The star arboricity of the complete regular multipartite graphs, preprint. · Zbl 0737.05038
[9] J. Akiyama and I. Saito,A comment on the linear arboricity for regular multigraphs, to appear.
[10] B. Bollobás,Random Graphs, Academic Press, London, 1985, p. 11.
[11] J. C. Bermond, J. L. Fouquet, M. Habib and B. Peroche,On linear k-arboricity, Discrete Math.43 (1984), 123–132. · Zbl 0556.05054 · doi:10.1016/0012-365X(84)90075-X
[12] J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, Macmillan Press, London, 1976. · Zbl 1226.05083
[13] H. Enomoto,The linear arboricity of 5-regular graphs, Technical Report, Dept. of Information Sci., Univ. of Tokyo, 1981. · Zbl 0475.05078
[14] P. Erdös and L. Lovász,Problems and results on 3-chromatic hypergraphs and some related questions, inInfinite and Finite Sets (A. Hajnalet al., eds.), North-Holland, Amsterdam, 1975, pp. 609–628.
[15] H. Enomoto and B. Peroche,The linear arboricity of some regular graphs, J. Graph Theory8 (1984), 309–324. · Zbl 0581.05017 · doi:10.1002/jgt.3190080211
[16] F. Guldan,The linear arboricity of 10-regular graphs, Math. Slovaca36 (1986), 225–228. · Zbl 0612.05050
[17] F. Guldan,Some results on linear arboricity, J. Graph Theory10 (1986), 505–509. · Zbl 0651.05029 · doi:10.1002/jgt.3190100408
[18] F. Harary,Covering and packing in graphs I., Ann. N.Y. Acad. Sci.175 (1970), 198–205. · Zbl 0226.05119
[19] M. Habib and B. Peroche,Some problems about linear arboricity, Discrete Math.41 (1982), 219–220. · Zbl 0486.05053 · doi:10.1016/0012-365X(82)90209-6
[20] M. Habib and B. Peroche,La k-arboricité linéaire des arbres, inCombinatorial Mathematics, Annals of Discrete Math.17, North-Holland, Amsterdam, 1983. · Zbl 0523.05025
[21] A. Nakayama and B. Peroche,Linear arboricity of digraphs, Networks17 (1987), 39–53. · Zbl 0649.05029 · doi:10.1002/net.3230170104
[22] B. Peroche,On partition of graphs into linear forests and dissections, preprint.
[23] J. Petersen,Die Theorie der regulären Graphs, Acta Math.15 (1891), 193–220. · JFM 23.0115.03 · doi:10.1007/BF02392606
[24] J. Spencer,Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987, pp. 61–62. · Zbl 0703.05046
[25] P. Tomasta,Note on linear arboricity, Math. Slovaca32 (1982), 239–242. · Zbl 0494.05047
[26] V. Vizing,On an estimate of the chromatic class of a p graph, Diskret Analiz.3 (1964), 25–30.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.