Colouring random 4-regular graphs

We show that a random 4-regular graph asymptotically almost surely (a.a.s.) has chromatic number 3. The proof uses an efficient algorithm which a.a.s. 3-colours a random 4-regular graph. The analysis includes use of the differential equation method, and exponential bounds on the tail of random variables associated with branching processes. A substantial part of the analysis applies to random d-regular graphs in general.