Backtracking | Set 5 (m Coloring Problem) | GeeksforGeeks

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.
Backtracking Algorithm
The idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, we check for safety by considering already assigned colors to the adjacent vertices. If we find a color assignment which is safe, we mark the color assignment as part of solution. If we do not a find color due to clashes then we backtrack and return false.

/* A utility function to check if the current color assignment

   is safe for vertex v */

bool isSafe (int v, bool graph[V][V], int color[], int c)

{

    for (int i = 0; i < V; i++)

        if (graph[v][i] && c == color[i])

            return false;

    return true;

}

/* A recursive utility function to solve m coloring problem */

bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)

{

    /* base case: If all vertices are assigned a color then

       return true */

    if (v == V)

        return true;

    /* Consider this vertex v and try different colors */

    for (int c = 1; c <= m; c++)

    {

        /* Check if assignment of color c to v is fine*/

        if (isSafe(v, graph, color, c))

        {

           color[v] = c;

           /* recur to assign colors to rest of the vertices */

           if (graphColoringUtil (graph, m, color, v+1) == true)

             return true;

            /* If assigning color c doesn't lead to a solution

               then remove it */

           color[v] = 0;

        }

    }

    /* If no color can be assigned to this vertex then return false */

    return false;

}

bool graphColoring(bool graph[V][V], int m)

{

    // Initialize all color values as 0. This initialization is needed

    // correct functioning of isSafe()

    int *color = new int[V];

    for (int i = 0; i < V; i++)

       color[i] = 0;

    // Call graphColoringUtil() for vertex 0

    if (graphColoringUtil(graph, m, color, 0) == false)

    {

      printf("Solution does not exist");

      return false;

    }

    // Print the solution

    printSolution(color);

    return true;

}

Read full article from Backtracking | Set 5 (m Coloring Problem) | GeeksforGeeks