On the chromatic number of random d-regular graphs

In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k−1)log(k−1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k−1 or k. If moreover d>(2k−3)log(k−1), then the value k−1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of equitable k-colourings, where a colouring is equitable if the number of vertices of each colour is equal.