Ask Your Question
0

Recursive Algorithm for Graph Coloring

asked 2016-07-07 12:53:25 -0500

JEA gravatar image

In a 2014 article by Exoo, Ismailescu, and Lim ("On the Chromatic Number of R^4"), a recursive algorithm is described that verifies the absence of a proper $k$-coloring of a graph $G$. The authors include only the following description of the algorithm.

"[The program is] based on the following recursive procedure that does an exhaustive search for a $K$-coloring of a graph of order $N$. It employs a global variable color, an array of order $N$, which records the color of each vertex $v$ for $1 \leq v \leq N$. The search is initiated with the call DFS(1)."

procedure DFS(v):
    Local variable: FCSet - the set of feasible colors for vertex v.
    if v > N:
        All vertices have been colored, report G is K-colorable.
        Exit.
    end if
    FCSet = {1 ... K}
    for u = 1 to v-1:
        if u is adjacent to v:
            FCSet = FCSet - color(u)
        end if
    end for
    for c in FCSet:
        color(v) = c
        DFS(v+1)
    end for 
end procedure

I am having difficulty implementing this algorithm in Sage. Given the nature of the program, I thought Java would be a more natural programming language to use for this algorithm, but I'm afraid I am not familiar with Java syntax.

Any help with implementing this algorithm would be greatly appreciated!

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2016-07-07 14:00:10 -0500

FrédéricC gravatar image

updated 2016-07-07 14:02:42 -0500

Here is a try

def kcolor(G, K):
    """
    test k-coloring
    """
    N = len(G)

    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, [0] * N))

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-07-07 12:53:25 -0500

Seen: 90 times

Last updated: Jul 07 '16