Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications

Marthe Bonamy, Thomas Perrett, Luke Postle

Let $G$ be a graph with chromatic number $\chi$, maximum degree $\Delta$ and clique number $\omega$. Reed's conjecture states that $\chi \le \lceil (1-\epsilon )(\Delta +1)+\epsilon \omega \rceil$ for…