On the chromatic number of random regular graphs
arXiv:1308.4287
Abstract
Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if d<d_{k-col} and non-k-colorable w.h.p. if d>d_{k-col}.
References in corpus (4)
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Random regular graphs of non-constant degree: Concentration of the chromatic number
- The Chromatic Number of Random Regular Graphs