# 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! – daniel pehoushek Apr 11 '17 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. – daniel pehoushek Mar 28 '17 at 11:11
• This result is for k at least some constant k_0. – David Wood Mar 29 '17 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. – daniel pehoushek Apr 2 '17 at 11:54