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.

Improve this question
$\endgroup$
1
  • 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
    Commented Apr 11, 2017 at 10:55

2 Answers 2

Reset to default
6
$\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)]$.

Improve this answer
$\endgroup$
2
  • 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
    Commented Mar 28, 2017 at 11:11
  • $\begingroup$ This result is for k at least some constant k_0. $\endgroup$
    – David Wood
    Commented Mar 29, 2017 at 10:12
3
$\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"

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 2, 2017 at 11:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .