Greedy colouring with two precoloured neighbours
ID: greedy-colouring-with-two-precoloured-neighbours
Let have two nonadjacent neighbours in a finite graph , with connected. Then . Give one common colour. In a spanning tree of the remaining graph rooted at , order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before has an uncoloured parent, so at most colours are forbidden there. At , the two initial neighbours use the same colour, so again at most distinct colours are forbidden. This constructs a proper colouring from a palette of colours. It is a useful local step in Brooks' theorem.
New to topics? Read the docs here!