The graph coloring problem is the following: 

COLORING: 

Data: adjacency matrix M of an m-vertex undirected graph. 

Decide: if there exists a vector v € {bleu, rouge, vert}msuch that for every edge (a, b) in the graph, v[a] v[b]. 

a- Sketch a backtracking algorithm colo(M) for Coloring. Hint. Think of what might be a k-promising vector, 0 Sk Sm. 

b- Even if no deterministic polynomial time algorithm solving Coloring is known, could you turn your algorithm above into a polynomial time Las Vegas algorithm? (Explain.)

Answer rating: 100% (QA)

a Here is a sketch of a backtracking algorithm coloM for the graph coloring problem 1 Initialize an ... View the full answer