{"id":2073,"date":"2020-06-12T11:42:30","date_gmt":"2020-06-12T11:42:30","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2073"},"modified":"2022-11-18T11:38:26","modified_gmt":"2022-11-18T11:38:26","slug":"m-coloring-problem","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/m-coloring-problem\/","title":{"rendered":"M Coloring Problem"},"content":{"rendered":"

\"\"<\/p>\n

Given an undirected graph and M<\/code> colors, the problem is to find if it is possible to color the graph with at most M<\/code> colors or not.<\/p>\n

<\/strong><\/u><\/a><\/p>\n

How to Solve M Coloring Problem :<\/h2>\n

Idea is to assign different colors (1-M)<\/code> to all the adjacent vertices. If at any point the color of any two adjacent vertices are same then we say it is not possible, otherwise it is.<\/p>\n

\"\"<\/p>\n

How backtracking Help:<\/h2>\n

We will use backtracking to solve the above problem.<\/p>\n

Backtracking<\/strong> is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.<\/p>\n

We will take a color array color[]<\/code> to store M<\/code> colours. Now iterate through color[]<\/code> , then we will assign each colour to all vertices one-by-one. If any colour assignment does not match the constraints then we will backtrack and unassign the colour which has been assigned to the vertex earlier. If the vertex count reaches the total number of vertices we will return true, and if none of the assignment matches the given condition (adjacent vertices must have different colours) then we will return false.<\/p>\n

Algorithm to Solve M Coloring Problem:<\/h2>\n

colour()<\/strong>:<\/p>\n

    \n
  1. If index == number.of.vertices<\/code>, return TRUE.<\/li>\n
  2. else, for every k= 1<\/code> to M<\/code> :\n
      \n
    • assign color to the current vertex, v<\/code>, (color[v]=k<\/code>)<\/li>\n
    • if colour(graph,vertex+1,color)==TRUE, return true<\/li>\n
    • else ,<\/li>\n
    • mark the colour as unassigned, (colour[v]=0<\/code>) (backtracking step).<\/li>\n
    • If none of the combination satisfies, return FALSE.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

      Complexity Analysis :<\/h3>\n

      In this method each vertex has M<\/code> different choices of colors. So the total time complexity<\/strong> is MV<\/sup> , where M<\/code> is the number of colours and V<\/code> is the number of vertices.<\/p>\n

      Program to Solve M Coloring Problem:<\/h2>\n\t\t\t\t\t\t