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

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journalArticlepeer-review

122 Scopus citations

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
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

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