Article contents
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
Published online by Cambridge University Press: 01 September 2007
Abstract
Let d=1≤d1≤ d2≤···.≤ dn be a non-decreasing sequence of n positive integers, whose sum is even. Let 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
. 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
is Θ(d/ln d). This condition is satisfied by graphs with exponential tails as well those with power law tails.
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2007
References
- 7
- Cited by