# Colorability of random regular graphs?

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.

• Theorem 1.1 in the answer implies tightness in the almost all results. The 5 colorability result is well known. The 9 and 13 regular results are not well known. Thanks! Apr 11, 2017 at 10:55

A pretty complete analysis of the chromatic number of random regular graphs can be found here: "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)]$.

• The paper says: Theorem 1.1 There is a sequence (εk)k≥3 with limk→∞ εk = 0 such that the following is true. 1. If d ≤ (2k − 1) ln k − 2 ln 2 − εk, then G(n, d) is k-colorable w.h.p. 2. If d ≥ (2k − 1) ln k − 1 + εk, then G(n, d) fails to be k-colorable w.h.p. Mar 28, 2017 at 11:11
• This result is for k at least some constant k_0. Mar 29, 2017 at 10:12

There is a large literature on this. Search for the following papers:

"Almost all graphs with average degree 4 are 3-colorable"

"5-Regular Graphs are 3-Colorable with Positive Probability"

"On the chromatic number of a random 5-regular graph"

• The 3 colorability of 5 regular graphs is well understood. There is nothing about 4 colorability of 9 regular graphs or 5 colorability of 13 regular graphs. The experimental results do agree with theorem 1.1 of the paper in the link above, and provide tight estimates for their error terms. Apr 2, 2017 at 11:54