Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-11T01:49:57.710Z Has data issue: false hasContentIssue false
  • English
  • Français

The Choice Number of Dense Random Graphs

Published online by Cambridge University Press:  01 January 2000

MICHAEL KRIVELEVICH
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: mkrivel@math.ias.edu)
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.

We prove that if the edge probability p(n) satisfies n−1/4+ε [les ] p(n) [les ] 3/4, where 0 < ε < 1/4 is a constant, then the choice number and the chromatic number of the random graph G(n, p) are almost surely asymptotically equal.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 1 , January 2000 , pp. 19 - 26
Copyright
2000 Cambridge University Press