|
Friday, November 14, 2008 |
|
|
|
|
On the chromatic number of random d-regular graphs |
|
|
Achlioptas and Moore have announced a proof that random d-regular graphs
asymptotically almost surely (a.a.s.) have chromatic number k-1, k, or k+1 where
k is the smallest integer satisfying d < 2(k-1)\log(k-1). For about half the
values of d, they showed it was k or k+1. We have shown that a.a.s. it is not
k+1, which determines the chromatic number a.a.s. for about half the values of
d. The proof applies the small subgraph conditioning method to the number of
balanced k-colourings, where a colouring is balanced if the number of vertices of
each colour is equal, and makes essential use of some of the earlier work of
Achlioptas and Naor. |