Tutte seminar - Nick Wormald

On the chromatic number of random d-regular graphs

Abstract:

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.

This is joint work with Graeme Kemkes and Xavier Perez.