Vfrdtyky

I have to find out the time complexity of graph coloring problem using backtracking. I have found somewhere it is O(n*m^n) where n=no vertex and m= number of color.

Suppose my code is given below how to find time complexity?

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;

}



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

{

    if (v == V)

        return true;



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

    {

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

        {

           color[v] = c;



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

             return true;



           color[v] = 0;

        }

    }



    return false;

}

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

{

    int *color = new int[V];

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

       color[i] = 0;



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

    {

      printf("Solution does not existn");

      return false;

    }



    printSolution(color);

    return true;

}

void printSolution(int color)

{

    printf("Solution Exists:"

            " Following are the assigned colors n");

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

      printf(" %d ", color[i]);

    printf("n");

}