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

Simple item page
dc.creatorAchlioptas, Dimitris
dc.creatorNaor, Assaf
dc.date2007-06-12
dc.date.accessioned2026-07-07T08:05:18Z
dc.date.available2026-07-07T08:05:18Z
dc.descriptionGiven d \in (0,infty) 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.
dc.description17 pages, published version
dc.identifierhttps://arxiv.org/abs/0706.1725
dc.identifierhttp://arxiv.org/abs/0706.1725
dc.identifierAnn. of Math. (2) 162 (2005), no. 3, 1335--1351
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/130243
dc.subjectProbability
dc.subject60C05
dc.titleThe two possible values of the chromatic number of a random graph
dc.typetext

Files

Collections

arXiv