Print all k-colorable configurations of the graph (Vertex coloring of graph)

Given a graph, find if it is k-colorable or not and print all possible configuration of assignment of colors to its vertices.


The vertex coloring is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color. A coloring using at most k colors is called a (proper) k-coloring and graph that can be assigned a (proper) k-coloring is k-colorable.

For example, consider below graph,
  graph-coloring

It can be 3-colored in many ways
graph-coloring-soln-2  graph-coloring-soln-3  graph-coloring-soln-1

Please note that we can’t color the above graph using 2 colors. i.e. it is not 2-colorable.

 


 

We can use backtracking to solve this problem. The idea is to try all possible combinations of colors for the first vertex in the graph and recursively explore remaining vertices to check if they will lead to the solution or not. If current configuration doesn’t result in solution, we backtrack. Note that we assign any color to a vertex only if its adjacent vertices share the different colors.

 
C++ implementation –
 

Download   Run Code

Output:

BLUE    GREEN   BLUE    RED     RED     GREEN
BLUE    GREEN   GREEN   BLUE    RED     GREEN
BLUE    GREEN   GREEN   RED     RED     GREEN
BLUE    RED     BLUE    GREEN   GREEN   RED
BLUE    RED     RED     BLUE    GREEN   RED
BLUE    RED     RED     GREEN   GREEN   RED
GREEN   BLUE    BLUE    GREEN   RED     BLUE
GREEN   BLUE    BLUE    RED     RED     BLUE
GREEN   BLUE    GREEN   RED     RED     BLUE
GREEN   RED     GREEN   BLUE    BLUE    RED
GREEN   RED     RED     BLUE    BLUE    RED
GREEN   RED     RED     GREEN   BLUE    RED
RED     BLUE    BLUE    GREEN   GREEN   BLUE
RED     BLUE    BLUE    RED     GREEN   BLUE
RED     BLUE    RED     GREEN   GREEN   BLUE
RED     GREEN   GREEN   BLUE    BLUE    GREEN
RED     GREEN   GREEN   RED     BLUE    GREEN
RED     GREEN   RED     BLUE    BLUE    GREEN

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂