Colouring a graph frugally
Every graph with maximum degree \(\Delta\geq\Delta_0\) has a proper \((\Delta+1)\)-coloring in which every color class has at most \(\log^8\Delta\) elements in the neighborhood of any vertex. If \(\beta\geq 1\) and the maximum degree is \(\delta\geq\Delta_\beta\) then there is a \(\max((\beta+1)\Delta,e^3\Delta^{1+{1\over\beta}})\)-coloring in which every color class has at most \(\beta\) elements in the neighborhood of any vertex. An example of Noga Alon gives that this is essentially best possible.
scientific article; zbMATH DE number 1261163