A graph coloring implementation

Given a set of vertices and their neighbour sets, the following Python script computes the graph coloring number of the corresponding graph.

#!/usr/bin/python

def coloring(V):
        l = 0
        col = {}
        fc = V.pop(0)
        col[fc] = 1
        for v in V:
                col[v] = -1
        for v in V:
                c = []
                for n in N[v]:
                        if col[n] > 0:
                                c.append(col[n])
                cl = 1
                while cl in c:
                        cl += 1
                col[v] = cl
        l = max(col, key=col.get)
        return l

V = [1,2,3,4]
N = {1: [2,3], 2: [1,3,4], 3: [1,2,4], 4: [2,3]}
print coloring(V)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License