Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.