An algorithm is described for colouring the vertices of a graph using the minimum number of colours possible so that any two adjacent vertices are coloured differently. The algorithm can produce all the optimal independent ways of colouring the graph. In the process of deriving the algorithm the concept of the ‘maximal’ internally stable sets (Berge, 1962) is generalised to more than one group of sets.
No takes yet. Share an insight, caveat, or question.
N. Christofides (1971) studied this question.