At what density is the chromatic number of a random graph r?

Problem (proposed by Erdös \( ^{[1]}\))
Let \(G\) denot a random graph on \(n\) vertices and \(cn\) edges. What is the smallest \(c = c(r) \) for which the probability that the chromatic number \(r\) is at least some constant strictly greater than \( 0 \) and independent of n?

This is open except for \( r=3\) (see \( ^{[1]}\)). Łuczak \( ^{[2]}\) gave an asymptotic estimate:

\(\displaystyle c(r) = (1+o(1)) 2 r \log r . \)
However, the exact values are not known.

In 1997, Alon and Krivelevich \( ^{[4]}\) showed that in many sparse cases the chromatic number concentrated on just two values.

In 2009, Kemkes, Pérez-Giménez, and Wormald \( ^{[3]}\) showed that for any fixed d, random d-regular graphs asymptotically almost surely can be colored with k colors, where k is the smallest integer satisfying \( d<2(k-1)\log(k-1)\). Furthermore they showed if \( d>(2k-3)\log(k-1)\), then the value \( k-1\) is discarded and thus the chromatic number is exactly determined.

Bibliography
1 N. Alon, J. H. Spencer and P. Erdös, The Probabilistic Method, Wiley and Sons, New York, 1992. (Link To sample sections.)
2 T. Łuczak, On the chromatic number of random graphs, Combinatorica 11 (1991), 45-54.
3 Kemkes, Pérez-Giménez, and Wormald, On the chromatic number of random d-regular graphs , Advances in Mathematics (2010) Volume 223, Issue 1, 300-328
4 N. Alon and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997) no. 3, 303-313