= Greedy colouring with two precoloured neighbours
Let $x$ have two nonadjacent <neighbours> $y,z$ in a finite <graph> $G$, with $G-\{y,z\}$ <connected>. Then $\chi(G)\leq\Delta(G)$. Give $y,z$ one common colour. In a <spanning tree> of the remaining <graph> rooted at $x$, order <vertices> from larger to smaller <distance> from the <root> and colour greedily in that order. Every <vertex> before $x$ has an uncoloured parent, so at most $\Delta(G)-1$ colours are forbidden there. At $x$, the two initial <neighbours> use the same colour, so again at most $\Delta(G)-1$ distinct colours are forbidden. This constructs a proper <colouring> from a palette of $\Delta(G)$ colours. It is a useful local step in <Brooks' theorem>.
Back to article page
