On the chromatic number of random d-regular graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1