2004/07/11 by Dimitris Achlioptas, Cristopher Moore
Physics and Astronomy · Mathematics · #cond-mat.dis-nn #cond-mat.stat-mech #math.CO #math.PR
published as Proc. RANDOM 2004
arxiv created 2004/07/11 · arxiv updated 2009/12/01
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2, and that if (2k-1) log k < d < 2k log k then the chromatic number is either k+1 or k+2.