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∆² 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.