Revision history [back]

Here is a try

def kcolor(G, K):
    """
    test k-coloring
    """
    N = len(G)
    color = [0] * N
    found = False

    def DFS(v, color):
        if v >= N:
            print color
            return True
            # All vertices have been colored, report G is K-colorable.
        FCSet = list(range(K))
        for u in G.neighbors(v):
            if u < v and color[u] in FCSet:
                FCSet.remove(color[u])

        for c in FCSet:
            color[v] = c
            if DFS(v + 1, color):
                return True

    return bool(DFS(0, color))

Here is a try

def kcolor(G, K):
    """
    test k-coloring
    """
    N = len(G)
    color = [0] * N
    found = False

    def DFS(v, color):
        if v >= N:
            print color
            return True
            # All vertices have been colored, report G is K-colorable.
        FCSet = list(range(K))
        for u in G.neighbors(v):
            if u < v and color[u] in FCSet:
                FCSet.remove(color[u])

        for c in FCSet:
            color[v] = c
            if DFS(v + 1, color):
                return True

    return bool(DFS(0, color))

Here is a try

def kcolor(G, K):
    """
    test k-coloring
    """
    N = len(G)
    color = [0] * N
    found = False

    def DFS(v, color):
        if v >= N:
            print color
            return True
            # All vertices have been colored, report G is K-colorable.
        FCSet = list(range(K))
        for u in G.neighbors(v):
            if u < v and color[u] in FCSet:
                FCSet.remove(color[u])

        for c in FCSet:
            color[v] = c
            if DFS(v + 1, color):
                return True

    return bool(DFS(0, color))
[0] * N))

Note that it assumes that the vertices are numbered from 0 to N-1, which is the usual sage convention.