Asymptotically optimal frugal colouring

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