m-Coloring Problem: Given m colors c₁, c₂, ..., c_m, and an undirected graph G(V,E) we seek to assign a color to each vertex such that for any edge (u,v) E, u and v are assigned different colors. Is the graph G m-colorable? If yes, then return the color of each vertex. If not, then return a message "The graph cannot be m-colored".

Design a backtracking algorithm to solve the m-coloring problem using the general framework discussed in class. All other solutions will not receive credit.

//define variables used

coloring(m, G) // add your pseudocode here

r-coloring(k, m, G)

//add your pseudocode here

color_ok(k, G)

//add your pseudocode here

(8 pts) Write the pseudo-code (2 pts) Analyze the worst-case running time of your algorithm.