Tutte seminar - Nick Wormald
On the chromatic number of random d-regular graphs
Speaker: | Nick Wormald |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
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).