Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T06:27:07.295Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number

Published online by Cambridge University Press:  06 September 2002

COLIN COOPER,
ALAN FRIEZE,
BRUCE REED and
OLIVER RIORDAN
COLIN COOPER
Affiliation:
Department of Mathematical and Computing Sciences, Goldsmiths College, University of London, New Cross, London SE14 6NW, England (e-mail: c.cooper@gold.ac.uk)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: alan@random.math.cmu.edu)
BRUCE REED
Affiliation:
Equipe Combinatoire, CNRS, Université de Paris VI, 4 Place Jussieu, Paris 75005, France (e-mail: reed@ecp6.jussieu.fr)
OLIVER RIORDAN
Affiliation:
Trinity College, Cambridge CB2 1TQ, England (e-mail: omr10@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let r = r(n) → ∞ with 3 [les ] r [les ] n1−η for an arbitrarily small constant η > 0, and let Gr denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set {1, 2, …, n}. We prove that, with probability tending to 1 as n → ∞, Gr has the following properties: the independence number of Gr is asymptotically 2n log r/r and the chromatic number of Gr is asymptotically r/2nlogr.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 4 , July 2002, pp. 323 - 341
Copyright
2002 Cambridge University Press