Naive Approach for M-Coloring Problem

Generate all possible configurations of colors. Since each node can be colored using any of the m available colors, the total number of color configurations possible is m^V. After generating a configuration of color, check if the adjacent vertices have the same color or not. If the conditions are met, print the combination.

Time Complexity: O(m^V). There is a total O(m^V) combination of colors
Auxiliary Space: O(V). The Recursive Stack of graph coloring(…) function will require O(V) space.

Given an undirected graph and a number m, the task is to color the given graph with at most m colors such that no two adjacent vertices of the graph are colored with the same color

Note: Here coloring of a graph means the assignment of colors to all vertices

Below is an example of a graph that can be colored with 3 different colors:

Examples: 

Input:  graph = {0, 1, 1, 1},
                         {1, 0, 1, 0},
                         {1, 1, 0, 1},
                         {1, 0, 1, 0}
Output: Solution Exists: Following are the assigned colors: 1  2  3  2
Explanation: By coloring the vertices with following colors,
                      adjacent vertices does not have same colors

Input: graph = {1, 1, 1, 1},
                         {1, 1, 1, 1},
                         {1, 1, 1, 1},
                         {1, 1, 1, 1}

Output: Solution does not exist
Explanation: No solution exits