ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 07 Jul 2016 14:00:10 -0500Recursive Algorithm for Graph Coloringhttp://ask.sagemath.org/question/34051/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! Thu, 07 Jul 2016 12:53:25 -0500http://ask.sagemath.org/question/34051/recursive-algorithm-for-graph-coloring/Answer by FrédéricC for <p>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.</p>
<p>"[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 <em>color</em>, 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)."</p>
<pre><code>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
</code></pre>
<p>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. </p>
<p>Any help with implementing this algorithm would be greatly appreciated! </p>
http://ask.sagemath.org/question/34051/recursive-algorithm-for-graph-coloring/?answer=34052#post-id-34052Here 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.Thu, 07 Jul 2016 14:00:10 -0500http://ask.sagemath.org/question/34051/recursive-algorithm-for-graph-coloring/?answer=34052#post-id-34052