= Colour savings from sparse neighbourhoods
If each neighbourhood misses a fixed positive fraction of the possible pairs at a large degree bound, randomly assign about half that many colours and erase vertices with monochromatic incident edges. A nonadjacent neighbour pair can share a retained colour, giving a <neighbour-colour saving>. Write the number of successful repeated colours as a difference of two <certifiable functions>: colours with a nonadjacent pair, minus those for which a neighbour loses that colour. Both change by at most two under one-coordinate changes and have constant-size certificates. <Talagrand's convex distance inequality> and the <Lovász local lemma> make their linear expected saving simultaneous at all high-degree vertices; low-degree vertices have slack already. This yields a colouring using a fixed positive fraction fewer than the degree bound.
Back to article page
