Combinatorics, Probability and Computing

Paper

On the Chromatic Number of Random Graphs with a Fixed Degree Sequence

ALAN FRIEZEa1, MICHAEL KRIVELEVICHa2 and CLIFF SMYTHa3

a1 Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, USA (e-mail: alan@random.math.cmu.edu)

a2 Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@post.tau.ac.il)

a3 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail: csmyth@math.mit.edu)

Abstract

Let d=1≤d1d2≤···.≤ dn be a non-decreasing sequence of n positive integers, whose sum is even. Let $\mathbb G_{n,{\bf d}$ denote the set of graphs with vertex set [n]={1,2,. . .., n} in which the degree of vertex i is di. Let Gn,d be chosen uniformly at random from $\mathbb G_{n,{\bf d}$. Let d=(d1+d2+···.+dn)/n be the average degree. We give a condition on d under which we can show that w.h.p. the chromatic number of $\mathbb G_{n,{\bf d}$ is Θ(d/ln d). This condition is satisfied by graphs with exponential tails as well those with power law tails.

(Received January 25 2006)

(Revised November 14 2006)

Footnotes

Supported in part by NSF grant CCR-0200945.

Research supported in part by USA–Israel BSF grant 2002-133 and by grants 64/01 and 526/05 from the Israel Science Foundation.