The Chromatic Number of Random Regular Graphs

Details The Chromatic Number of Random Regular Graphs The Chromatic Number of Random Regular Graphs

2004-07-11

arxiv.org/abs/cond-mat/0407278v1

Proc. RANDOM 2004

Physics

Condensed Matter

Disordered Systems and Neural Networks

Scientific paper

Given any integer d >= 3, let k be the smallest integer such that d < 2k log
k. We prove that with high probability the chromatic number of a random
d-regular graph is k, k+1, or k+2, and that if (2k-1) \log k < d < 2k \log k
then the chromatic number is either k+1 or k+2.

Affiliated with

Also associated with

No associations

Rating

The Chromatic Number of Random Regular Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Chromatic Number of Random Regular Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Chromatic Number of Random Regular Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-158236