Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-17T17:01:02.228Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Thickness of Sparse Random Graphs

Published online by Cambridge University Press:  12 September 2008

Colin Cooper
Colin Cooper
Affiliation:
School of Mathematical Studies, University of North London, 2-16 Eden Grove, London N7 8EA
Get access Rights & Permissions [Opens in a new window]

Abstract

The thickness of sparse random graphs in the model Gn, p is closely related to the arboricity, provided p(n) is suitably small. This allows us to identify a range of p(n) for which the thickness is approximately np/2.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 4 , December 1992 , pp. 303 - 309
Copyright
Copyright © Cambridge University Press 1992

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]Ajtai, M., Komlós, J. and Szemerédi, E. (1979) Topological complete subgraphs in random graphs. Studia Scientiarum Mathematicarum Hungarica 14 293–297.Google Scholar
[2]Bollobás, B. (1985) Random Graphs, Academic Press.Google Scholar
[3]Chvátal, V. (1991) Almost all graphs with 1.44n edges are 3 colourable. Random Structures and Algorithms 2 11–28.CrossRefGoogle Scholar
[4]Frieze, A. M. and Luczak, T. (1990) Edge disjoint trees in random graphs. Periodica Mathematica Hungarica 21 35–37.CrossRefGoogle Scholar
[5]Frieze, A. M. and Molloy, M. (1992) Private communication.Google Scholar
[6] Nash-Williams, C. St. J. A. (1964) Decomposition of finite graphs into forests. J. London Math. Soc. 39 12.CrossRefGoogle Scholar
[7]Pittel, B. (1990) On tree census and the giant component in sparse random graphs. Random Structures and Algorithms 1 311–342.CrossRefGoogle Scholar