Sharp concentration of the chromatic number on random graphs G n, p

Eli Shamir, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

The distribution of the chromatic number on random graphs Gn, p is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.

Original languageEnglish (US)
Pages (from-to)121-129
Number of pages9
JournalCombinatorica
Volume7
Issue number1
DOIs
StatePublished - Mar 1987

Keywords

  • 05 C 15
  • 60 C 05

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Sharp concentration of the chromatic number on random graphs G n, p'. Together they form a unique fingerprint.

Cite this