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 factor in the O(-) term. We also provide an efficient algorithm to produce such a colouring.
展开▼
