Abstract
Determining the chromatic number of random graphs is one of the longest-standing challenges in probabilistic combinatorics. For the Erdös-Rényi model, the single most intensely studied model in the random graphs literature, the question dates back to the seminal 1960 paper that started the theory of random graphs. Apart from that, the model that has received the most attention certainly is the random regular graph. We provide an almost complete solution to the chromatic number problem on the random d-regular graph on n vertices where d remains fixed as n tends to infinity. For every integer k exceeding a certain constant k_0 we identify a number d(k) such that the random d-regular graph is k-colorable with probability tending to 1 as n tends to infinity if d<d(k) and non-k-colorable with probability tending to 1 as n tends to infinity if d>d(k).
This is joint work with Amin Coja-Oghlan and Charilaos Efthymiou.