An improved procedure for colouring graphs of bounded local density

We develop an improved bound for the chromatic number of graphs of maximum degree ∆ under the assumption that the number of edges spanning any neighbourhood is at most (1σ ) ∆ 2 for some fixed 0 < σ < 1. The leading term in the reduction of colours achieved through this bound is best possible as σ → 0. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture. We prove that the strong chromatic index is at most 1.772∆ 2 for any graph G with sufficiently large maximum degree ∆. We prove that the chromatic number is at most 0.881(∆ + 1) + 0.119ω for any graph G with clique number ω and sufficiently large maximum degree ∆. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most (1σ )∆, and establish what may be considered first progress towards a conjecture of Vu.