Random regular graphs of non-constant degree: Concentration of the chromatic number
<|reference_start|>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 $\Gnd$ for $d=o(n^{1/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 $\Gnp$ with $p=\frac{d}{n}$. Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for $\Gnp$ for $p=n^{-\delta}$ where $\delta>1/2$. The main tool used to derive such a result is a careful analysis of the distribution of edges in $\Gnd$, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.<|reference_end|>
@article{ben-shimon2005random,
    title={Random regular graphs of non-constant degree: Concentration of the
  chromatic number},
    author={Sonny Ben-Shimon and Michael Krivelevich},
    journal={Discrete Mathematics, 309(12):4149--4161, 2009},
    year={2005},
    doi={10.1016/j.disc.2008.12.014},
    archivePrefix={arXiv},
    eprint={math/0511343},
    primaryClass={math.CO cs.DM math.PR}
}