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

Dimitris Achlioptas, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages587-593
Number of pages7
StatePublished - 2004
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004

Other

OtherProceedings of the 36th Annual ACM Symposium on Theory of Computing
CountryUnited States
CityChicago, IL
Period6/13/046/15/04

Keywords

  • Chromatic Number
  • Graph Coloring
  • Random Graphs

ASJC Scopus subject areas

  • Software

Cite this

Achlioptas, D., & Naor, A. (2004). The two possible values of the chromatic number of a random graph. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 587-593)