Asymptotically optimal frugal colouring

We prove that every graph with maximum degree Δ can be properly ( Δ + 1 ) -coloured so that no colour appears more than O ( log Δ / log log Δ ) times in the neighbourhood of any vertex. This is best possible up to the constant multiple in the O ( − ) term.