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

• 成果类型: Article
• 署名作者: Achlioptas, D; Naor, A
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2005.162.1335
• 发表日期: 2005
• 页码: 1335-1351
• 关键词: sharp concentration

摘要

Given d epsilon (0, infinity) 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 kd or k(d) + 1 almost surely.