An improved procedure for colouring graphs of bounded local density

We develop an improved bound for the chromatic number of graphs of maximum degree $\mathrm{\Delta }$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-\sigma )\left(\genfrac{}{}{0px}{}{\mathrm{\Delta }}{2}\right)$ for some fixed $0<\sigma <1$. The leading term in the reduction of colours achieved through this bound is best possible as $\sigma \to 0$. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erd\H{o}s-Ne\v{s}et\v{r}il conjecture and Reed’s conjecture. We prove that the strong chromatic index is at most $1.772{\mathrm{\Delta }}^2$ for any graph $G$ with sufficiently large maximum degree $\mathrm{\Delta }$. We prove that the chromatic number is at most $\lceil 0.881(\mathrm{\Delta }+1)+0.119\omega \rceil$ for any graph $G$ with clique number $\omega$ and sufficiently large maximum degree $\mathrm{\Delta }$. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-\sigma )\mathrm{\Delta }$, and establish what may be considered first progress towards a conjecture of Vu.