Given a graph G(V,E), with |V|=n and k<n(here k corresponds to number of colors), I am trying to create the set of all proper colorings of it in Python i.e. each v in V has a color which is different from its neighbor's.

My attempt: I was thinking of creating a list of all possible colorings first (there are k^n of them) and then go through this list to apply the constraint to get a list of proper colorings. In terms of data structures, I was thinking of using a dictionary for each coloring with the vertex number being the key, and the value being a list of lists. The first element of this list is the color of the vertex and the second is a list of its neighbors. In order to create all colorings, is there a recursive way to generate these colorings? The code for a random graph is:

def Graph(n):
    g={}
    for i in range(n):
        r=random.choice([i 1 for i in range(n)])
        v=[i for i in range(n)]
        v.remove(i)
        g[i]=random.sample(v,r)

    return g

CodePudding user response：

def fillRemainingColors(coloringSoFar,g):
    if all colors filled:
        return [coloringSoFar]
    else:
       Pick a uncolored spot to color
       coloringsToReturn = []
       For each possible color for that spot:
           newColoring = fill(coloringSoFar, spot, color)
           coloringsToReturn  = fillRemainingColors(newColoring,g)
       return coloringsToReturn