Random regular graphs of non-constant degree: Concentration of the chromatic number

Details Random regular graphs of non-constant degree: Concentration of the chromatic number Random regular graphs of non-constant degree: Concentration of the chromatic number

2005-11-14

arxiv.org/abs/math/0511343v5

Discrete Mathematics, 309(12):4149--4161, 2009

Mathematics

Combinatorics

18 pages

Scientific paper

10.1016/j.disc.2008.12.014

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model $\Gnd$ for $d=o(n^{1/5})$ is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model $\Gnp$ with $p=\frac{d}{n}$. Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for $\Gnp$ for $p=n^{-\delta}$ where $\delta>1/2$. The main tool used to derive such a result is a careful analysis of the distribution of edges in $\Gnd$, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.

Affiliated with

Also associated with

No associations

Rating

Random regular graphs of non-constant degree: Concentration of the chromatic number 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 Random regular graphs of non-constant degree: Concentration of the chromatic number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random regular graphs of non-constant degree: Concentration of the chromatic number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218798