<p>Almost all regular graphs with degree $k^2$ are $k+1$ colorable.</p>

<p>The near absence (finitude) of adjacent small cycles in random regular graphs as $N$ (the size of the graph) grows may help imply the truth, but any proof looks far away.
The conjecture is empirically true for $k=3$ (i.e. Almost all 9-regular graphs are 4 colorable).</p>

<p>Does this conjecture have a name, or better yet, is it true? </p>

CC BY-SA 3.0
2014-09-22T08:29:40.277Z
As N grows, the probability of the property being true approaches 1.  For 9-regular graphs, for example, N needs to be greater than about 125 for it to be likely to be 4 colorable.
daniel pehoushek
CC BY-SA 3.0
2014-09-22T13:35:28.047Z
The chromatic number of a random $d$-regular graph is $\Theta(d/\log d)$ a.s. See for example http://www.sciencedirect.com/science/article/pii/009589569290070E
Sasho Nikolov
CC BY-SA 3.0
2014-09-22T18:17:20.617Z
That appears to answer the question, so thank you.
daniel pehoushek
<graph-theory>
Regular graph coloring conjecture
daniel pehoushek
# Regular graph coloring conjecture

(Asked by: username_0 on 2014-09-22)

Almost all regular graphs with degree $k^2$ are $k+1$ colorable.

The near absence (finitude) of adjacent small cycles in random regular graphs as $N$ (the size of the graph) grows may help imply the truth, but any proof looks far away.
The conjecture is empirically true for $k=3$ (i.e. Almost all 9-regular graphs are 4 colorable).

Does this conjecture have a name, or better yet, is it true?

**Tags:** graph-theory

> **Comments:**
> **username_0**: As N grows, the probability of the property being true approaches 1.  For 9-regular graphs, for example, N needs to be greater than about 125 for it to be likely to be 4 colorable.  
> **username_1**: The chromatic number of a random $d$-regular graph is $\Theta(d/\log d)$ a.s. See for example http://www.sciencedirect.com/science/article/pii/009589569290070E  
> **username_0**: That appears to answer the question, so thank you.  

---

## 0 answers

