The two possible values of the chromatic number of a random graph

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journalArticle

94 Scopus citations

Abstract

Given d ∈ (0, ∞) let k d be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d/n) is either k d or k d + 1 almost surely.

Original languageEnglish (US)
Pages (from-to)1335-1351
Number of pages17
JournalAnnals of Mathematics
Volume162
Issue number3
DOIs
StatePublished - Dec 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'The two possible values of the chromatic number of a random graph'. Together they form a unique fingerprint.

  • Cite this