Extension of a partial colouring by neighbour-colour savings

ID: extension-of-a-partial-colouring-by-neighbour-colour-savings

In a proper partial graph coloring, let count coloured neighbours and count their distinct colours. The saving leaves available colours for only initially uncoloured neighbours. If the displayed inequality holds at every vertex, ordinary greedy completion succeeds. Each additionally coloured neighbour removes at most one available colour while also reducing the number of uncoloured neighbours by one.

New to topics? Read the docs here!