I have the following experimental results on random regular graphs. I would like to know current theory on colorability of random regular graphs.


Almost all 5 regular graphs are 3 colorable.


Almost all 9 regular graphs are 4 colorable.


Almost all 13 regular graphs are 5 colorable.


These appear to be tight experimentally. Are they?


Exhibiting such colorings is difficult as the size of the graph grows, and I have trouble with degree 9 and 13. I am particularly interested in degree 9 graphs, as these 4 coloring problems produce very difficult 4-CNFs for satisfiability programs. 


I am preparing a paper for Satisfiability 2017 on regular graph coloring, and would like references on known theory.



Colorability of random regular graphs?
A pretty complete analysis of the chromatic number of random regular graphs can be found [here](https://arxiv.org/abs/1308.4287): "On the chromatic number of random regular graphs." Roughly speaking, the chromatic number of a random $d$-regular graph is $k$, where $d \in [(2k-3)\ln(k-1), (2k-2)\ln(k-1)]$.


