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

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journalArticlepeer-review

Abstract

Given d ∈ (0, ∞) let kd 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 kd or kd + 1 almost surely.

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

ASJC Scopus subject areas

  • 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