Currently I am looking into register allocation using graph colouring
(also see Chaitin’s paper on the subject). The graph colouring problem also occurs when
trying to colour countries in a political world map where adjacent countries must have different colours.
I thought it would be interesting to try a minimal implementation in Scheme.
Feel free to suggest improvements in the comment section below .
A (undirected) graph is usually represented by a list of nodes (vertices) and a list of edges.
If there are no insular nodes, a list of edges is sufficient.
In Scheme (here GNU Guile implementation) one can do this as follows.
Using the argument of the minimum one can determine the node with lowest adjacency count.
Now one can recursively remove the node with lowest adjacency count and then assign colours starting with the last node and working backwards.
If an adjacent node has a colour already, another colour must be used.
And here is an example of coloring a graph with a few more nodes.