An improved procedure for colouring graphs of bounded local density
share
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.
READ FULL TEXT