Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T18:19:07.531Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost Every Graph can be Covered by Linear Forests

Published online by Cambridge University Press:  12 September 2008

Colin McDiarmid  and
Bruce Reed
Colin McDiarmid
Affiliation:
Department of Statistics, Oxford University, Oxford, UK
Bruce Reed
Affiliation:
Institut für Diskrete Mathematik, University of Bonn, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

A linear forest is the union of a set of vertex disjoint paths. Akiyama, Exoo and Harary, and independently Hilton, have conjectured that the edges of every graph of maximum degree Δ can be covered by linear forests. We show that almost every graph can be covered with this number of linear forests.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 3 , September 1995 , pp. 257 - 268
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Akiyama, J. and Chvátal, V. (1981) A short proof of the linear arboricity for cubic graphs. Bull. Liber. Arts & Sci., NMS no 2 1–3.Google Scholar
[2]Akiyama, J., Exoo, G. and Harary, F. (1980) Covering and packing in graph III. Cyclic and acyclic invariants. Maths Slovaka 30 405–417.Google Scholar
[3]Akiyama, J., Exoo, G. and Harary, F. (1981) Covering and packing in graphs IV: Linear arboricity. Networks 11 69–72.CrossRefGoogle Scholar
[4]Alon, N. (1988) The linear arboricity of graphs. Israel Journal of Mathematics 62 311–325.CrossRefGoogle Scholar
[5]Alon, N. (1994) Probabilistic methods in coloring and decomposition problems. Discrete Mathematics 127 31–46.CrossRefGoogle Scholar
[6]Alon, N. and Spencer, J. (1992) The Probabilistic Method, Wiley, New York.Google Scholar
[7]Bollobás, B. (1985) Random Graphs, Academic Press, New York.Google Scholar
[8]Chvátal, V. (1979) The tail of the hypergeometric distribution. Discrete Mathematics 25 285–287.CrossRefGoogle Scholar
[9]Enomoto, H. (1981) The linear arboricity of 5-regular graphs. Technical Report, Department of Information Science, University of Tokyo.Google Scholar
[10]Enomoto, H. and Peroche, B. (1984) The linear arboricity of some regular graphs. J. Graph Theory 8 309–324.CrossRefGoogle Scholar
[11]Guldan, F. (1986) The linear arboricity of 10-regular graphs. Math. Slovaka 36 225–228.Google Scholar
[12]Guldan, F. (1986) Some results on linear arboricity. J. Graph Theory 10 505–509.CrossRefGoogle Scholar
[13]Harary, F. (1970) Covering and packing in graphs I. Ann. N.Y. Acad. Sci. 175 198–205.CrossRefGoogle Scholar
[14]Hilton, A. J. W. (1982) Canonical edge-colourings of locally finite graphs. Combinatorica 2 37–51.CrossRefGoogle Scholar
[15]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.CrossRefGoogle Scholar
[16]McDiarmid, C. J. H. (1989) On the method of bounded differences, in Surveys in Combinatorics, 1989, Siemons, J. ed., London Mathematical Society Lecture Note Series 141, Cambridge University Press, 148–188.CrossRefGoogle Scholar
[17]McDiarmid, C. J. H. and Reed, B. A. (1990) The linear arboricity of random regular graphs. Random Structures and Algorithms 1 443–445.CrossRefGoogle Scholar
[18]Peroche, B. (1982) On partition of graphs into linear forests and dissections. Preprint.Google Scholar
[19]Tomasta, P. (1982) Note on linear arboricity. Math. Slovaka 32 239–242.Google Scholar