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

Dimitris Achlioptas; Assaf Naor

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

Dimitris Achlioptas, Assaf Naor

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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)
Title of host publication	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages	587-593
Number of pages	7
State	Published - 2004
Event	Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004

Other

Other	Proceedings of the 36th Annual ACM Symposium on Theory of Computing
Country/Territory	United States
City	Chicago, IL
Period	6/13/04 → 6/15/04

Keywords

Chromatic Number
Graph Coloring
Random Graphs

ASJC Scopus subject areas

Software

Cite this

@inproceedings{fdfc6b100d804365a605ddd160979743,

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

language = "English (US)",

pages = "587--593",

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

note = "Proceedings of the 36th Annual ACM Symposium on Theory of Computing ; Conference date: 13-06-2004 Through 15-06-2004",

}

TY - GEN

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

M3 - Conference contribution

AN - SCOPUS:4544292840

SP - 587

EP - 593

BT - 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

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this