4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – daniel pehoushek Apr 11 '17 at 10:55
5
$\begingroup$

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)]$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – daniel pehoushek Mar 28 '17 at 11:11
  • $\begingroup$ This result is for k at least some constant k_0. $\endgroup$ – David Wood Mar 29 '17 at 10:12
2
$\begingroup$

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"

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – daniel pehoushek Apr 2 '17 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.