COLORING A GRAPH FRUGALLY

We prove that any graph with maximum degree Delta sufficiently large, has a proper vertex colouring using a Delta + 1 colours such that each colour class appears at most log(8) Delta times in the neighbourhood of any vertex. We also show that for beta greater than or equal to 1, the minimum number of colours required to colour any such. graph so th at each vertex appears at most beta times in the neighbourhood of any vertex is theta(Delta + Delta(1+1/beta)/beta), showing in particular t hat when beta = log Delta/loglog Delta, such a colouring cannot always be achieved with O(Delta) colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.