k-Colouring when k is close to Δ

We discuss applications of a simple random colouring procedure, including a determination of the set of values k for which k-colourability of graphs with maximum degree Δ is NP-complete.