function graphColoring(graph, m, n, color[], vertex):
if vertex == n:
print(color) // all vertices are colored
return True
for c = 1 to m:
if isSafe(vertex, graph, color, c):
color[vertex] = c
if graphColoring(graph, m, n, color, vertex+1):
return True
color[vertex] = 0 // backtrack
return False
function isSafe(vertex, graph, color, c):
for each neighbor v of vertex:
if color[v] == c:
return False
return True
Colors = [R , G, B]
Inputs : graph, m (no. of colors = 3), n (no. of vertices = 4), color [], initial vertex = a
Step vertex try c neighbors' safe? action performed color[] (1..4) note
colors (by
vertex)
1 1=a R (no neighbors Yes assign color[1]=R, [R,0,0,0] start
colored yet) recurse → vertex=b
2 2=b R neighbor a → No skip color R, try [R,0,0,0] can't use R
color[1]=R next because (a,b)
edge
3 2=b G neighbor a → Yes assign color[2]=G, [R,G,0,0]
color[1]=R recurse → vertex=c
4 3=c R neighbor b → Yes assign color[1]=R, [R,G,R,0] can use R
color[2]=G recurse → vertex=d because no (a,c)
edge
5 4=d R neighbor a → No skip color R, try [R,G,R,0] can't use R
color[1]=R next because (a,d)
edge
6 4=d G neighbor a → Yes assign color[2]=G [R,G,R,G]
color[1]=R
neighbor c →
color[1]=R
7 4 — — — vertex == N → [R,G,R,G] solution found —
print [a,b,c,d] and algorithm stops
return True (no backtracking
needed)
Time Complexity of Graph Coloring
Worst Case:O(V * mV)
There are a total of O(m V) combinations of colors. For each attempted coloring of a vertex it will
call issafe(), and can have up to V–1 neighbors, so issafe() is O(V).
Best case:O(V)
V = {a, b}
C = {R, G}
