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

Abstract

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.

18 pages

Cited by in corpus (5)

• Exchangeable pairs, switchings, and random regular graphs
• Meyniel's conjecture holds for random d-regular graphs
• On the chromatic number of random regular graphs
• Eigenvalue fluctuations for random regular graphs
• On the chromatic number of random d-regular graphs