Skip to main content
SpringerLink
Log in

The linear arboricity of graphs

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G),\(la(G) \leqq [\frac{{\Delta + 1}}{2}].\). Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ0=Δ0(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ0. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  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.

  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.

    Google Scholar 

  5. J. Akiyama, G. Exoo and F. Harary,Covering and packing in graphs III. Cyclic and acyclic invariants, Math. Slovaca30 (1980), 405–417.

    MATH  MathSciNet  Google Scholar 

  6. J. Akiyama, G. Exoo and F. Harary,Covering and packing in graphs IV. Linear arboricity, Networks11 (1981), 69–72.

    Article  MATH  MathSciNet  Google Scholar 

  7. J. Akiyama and M. Kano,Path factors of a graph, in:Graph Theory and its Applications, Wiley and Sons, New York, 1984.

    Google Scholar 

  8. Y. Aoki,The star arboricity of the complete regular multipartite graphs, preprint.

  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.

    MATH  Google Scholar 

  11. J. C. Bermond, J. L. Fouquet, M. Habib and B. Peroche,On linear k-arboricity, Discrete Math.43 (1984), 123–132.

    Article  MathSciNet  Google Scholar 

  12. J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, Macmillan Press, London, 1976.

    Google Scholar 

  13. H. Enomoto,The linear arboricity of 5-regular graphs, Technical Report, Dept. of Information Sci., Univ. of Tokyo, 1981.

  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.

    Google Scholar 

  15. H. Enomoto and B. Peroche,The linear arboricity of some regular graphs, J. Graph Theory8 (1984), 309–324.

    Article  MATH  MathSciNet  Google Scholar 

  16. F. Guldan,The linear arboricity of 10-regular graphs, Math. Slovaca36 (1986), 225–228.

    MATH  MathSciNet  Google Scholar 

  17. F. Guldan,Some results on linear arboricity, J. Graph Theory10 (1986), 505–509.

    Article  MATH  MathSciNet  Google Scholar 

  18. F. Harary,Covering and packing in graphs I., Ann. N.Y. Acad. Sci.175 (1970), 198–205.

    MATH  Google Scholar 

  19. M. Habib and B. Peroche,Some problems about linear arboricity, Discrete Math.41 (1982), 219–220.

    Article  MATH  MathSciNet  Google Scholar 

  20. M. Habib and B. Peroche,La k-arboricité linéaire des arbres, inCombinatorial Mathematics, Annals of Discrete Math.17, North-Holland, Amsterdam, 1983.

    Google Scholar 

  21. A. Nakayama and B. Peroche,Linear arboricity of digraphs, Networks17 (1987), 39–53.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Article  MathSciNet  Google Scholar 

  24. J. Spencer,Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987, pp. 61–62.

    MATH  Google Scholar 

  25. P. Tomasta,Note on linear arboricity, Math. Slovaca32 (1982), 239–242.

    MATH  MathSciNet  Google Scholar 

  26. V. Vizing,On an estimate of the chromatic class of a p graph, Diskret Analiz.3 (1964), 25–30.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv, Israel

    N. Alon

Authors
  1. N. Alon
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant, by the Fund for Basic Research administered by the Israel Academy of Sciences and by a B.S.F. Bergmann Memorial grant.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alon, N. The linear arboricity of graphs. Israel J. Math. 62, 311–325 (1988). https://doi.org/10.1007/BF02783300

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02783300

Keywords

Search

Navigation