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

Dimitris Achlioptas; Assaf Naor

doi:10.4007/annals.2005.162.1335

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

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journal › Article › peer-review

127 Scopus citations

Abstract

Given d ∈ (0, ∞) let k_d 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 k_d or k_d + 1 almost surely.

Original language	English (US)
Pages (from-to)	1335-1351
Number of pages	17
Journal	Annals of Mathematics
Volume	162
Issue number	3
DOIs	https://doi.org/10.4007/annals.2005.162.1335
State	Published - 2005
Externally published	Yes

All Science Journal Classification (ASJC) codes

Mathematics (miscellaneous)

Access to Document

10.4007/annals.2005.162.1335

Cite this

@article{f2a1d24f89d34fc4a84a3cefb3e74d1a,

title = "The two possible values of the chromatic number of a random graph",

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.",

author = "Dimitris Achlioptas and Assaf Naor",

year = "2005",

doi = "10.4007/annals.2005.162.1335",

language = "English (US)",

volume = "162",

pages = "1335--1351",

journal = "Annals of Mathematics",

issn = "0003-486X",

publisher = "Department of Mathematics at Princeton University",

number = "3",

}

TY - JOUR

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

AU - Achlioptas, Dimitris

AU - Naor, Assaf

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/33745880378

UR - https://www.scopus.com/inward/citedby.url?scp=33745880378&partnerID=8YFLogxK

U2 - 10.4007/annals.2005.162.1335

DO - 10.4007/annals.2005.162.1335

M3 - Article

AN - SCOPUS:33745880378

SN - 0003-486X

VL - 162

SP - 1335

EP - 1351

JO - Annals of Mathematics

JF - Annals of Mathematics

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this