Let k be a fixed integer and fk(n, p) denote the probability that the random graph G(n, p) is k-colorable. We show that for k≥3, there exists dk(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1.
No takes yet. Share an insight, caveat, or question.
Achlioptas et al. (1999) studied this question.