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

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journalConference article

18 Scopus citations

Abstract

For every 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. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k + 1.

Original languageEnglish (US)
Pages (from-to)587-593
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Jan 1 2004
Externally publishedYes
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Chromatic Number
  • Graph Coloring
  • Random Graphs

Cite this