The concentration of the chromatic number of random graphs

Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticle

46 Scopus citations

Abstract

We prove that for every constant δ > 0 the chromatic number of the random graph G(n,p) with p = n-1/2-δ is asymptotically almost surely concentrated in two consecutive values. This implies that for any β < 1/2 and any integer valued function r(n)≤O(nβ) there exists a function p(n) such that the chromatic number of G(n,p(n)) is precisely r(n) asymptotically almost surely.

Original languageEnglish (US)
Pages (from-to)303-313
Number of pages11
JournalCombinatorica
Volume17
Issue number3
DOIs
StatePublished - Jan 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The concentration of the chromatic number of random graphs'. Together they form a unique fingerprint.

  • Cite this