Colouring a graph frugally (Q1280272): Difference between revisions

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.