Random regular graphs of non-constant degree: Concentration of the chromatic number

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model Gn,dGn,d for d=o(n1/5)d=o(n1/5) is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model G(n,p)G(n,p) with p=dn. Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for G(n,p)G(n,p) for p=n−δp=n−δ where δ>1/2δ>1/2. The main tool used to derive such a result is a careful analysis of the distribution of edges in Gn,dGn,d, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.