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

Dimitris Achlioptas; Assaf Naor

doi:10.1145/1007352.1007442

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

Dimitris Achlioptas, Assaf Naor

Research output: Contribution to journal › Conference article › peer-review

20 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	587-593
Number of pages	7
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1007352.1007442
State	Published - 2004
Externally published	Yes
Event	Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004

All Science Journal Classification (ASJC) codes

Software

Keywords

Chromatic Number
Graph Coloring
Random Graphs

Access to Document

10.1145/1007352.1007442

Cite this

@article{8fb240f61a8446fbb5c1b7b326d9447e,

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

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

keywords = "Chromatic Number, Graph Coloring, Random Graphs",

author = "Dimitris Achlioptas and Assaf Naor",

year = "2004",

doi = "10.1145/1007352.1007442",

language = "English (US)",

pages = "587--593",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

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

AU - Achlioptas, Dimitris

AU - Naor, Assaf

PY - 2004

Y1 - 2004

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

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

KW - Chromatic Number

KW - Graph Coloring

KW - Random Graphs

UR - http://www.scopus.com/inward/record.url?scp=4544292840&partnerID=8YFLogxK

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

U2 - 10.1145/1007352.1007442

DO - 10.1145/1007352.1007442

M3 - Conference article

AN - SCOPUS:4544292840

SN - 0734-9025

SP - 587

EP - 593

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 36th Annual ACM Symposium on Theory of Computing

Y2 - 13 June 2004 through 15 June 2004

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this