Colouring random 4-regular graphs

Lingsheng Shi, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)309-344
Number of pages36
JournalCombinatorics, Probability and Computing
Issue number2
Publication statusPublished - Mar 2007
Externally publishedYes

Cite this