Colouring graphs with sparse neighbourhoods: Bounds and applications

Let G be a graph with chromatic number chi, maximum degree Delta and clique number omega. Reed's conjecture states that chi <= [(1 - epsilon)(Delta + 1) + epsilon omega] for all epsilon <= 1/2. It was shown by King and Reed that, provided Delta is large enough, the conjecture holds for epsilon <= 1/130,000. In this article, we show that the same statement holds for epsilon <= 1/26, thus making a significant step towards Reed's conjecture. We derive this result from a general technique to bound the chromatic number of a graph where no vertex has many edges in its neighbourhood. Our improvements to this method also lead to improved bounds on the strong chromatic index of general graphs. We prove that chi(s)' (G) <= 1.835 Delta(G)(2) provided Delta(G) is large enough. (C) 2022 Published by Elsevier Inc.