An improved procedure for colouring graphs of bounded local density

Eoin Hurley, Rémi de Joannis de Verclos, Ross J. Kang

We develop an improved bound for the chromatic number of graphs of maximum degree $\Delta$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-σ)\bin…