# Recursive Algorithm for Graph Coloring

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 close merge delete

Sort by » oldest newest most voted

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.

more