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

• Autores: Dimitris Achlioptas, Assaf Naor
• Localización: Annals of mathematics, ISSN 0003-486X, Vol. 162, Nº 3, 2005, págs. 1333-1349
• Idioma: inglés
• DOI: 10.4007/annals.2005.162.1335
• Texto completo no disponible (Saber más ...)
• Resumen

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