m Coloring Problem | Backtracking |  ; Number of vertices in the graph ; A utility function to print solution ; check if the colored graph is safe or not ; check for every edge ; This function solves the m Coloring problem using recursion . It returns false if the m colours cannot be assigned , otherwise , return true and prints assignments of colours to all vertices . Please note that there may be more than one solutions , this function prints one of the feasible solutions . ; if current index reached end ; if coloring is safe ; Print the solution ; Assign each color from 1 to m ; Recur of the rest vertices ; Driver code ; Create following graph and test whether it is 3 colorable ( 3 ) -- - ( 2 ) | / | | / | | / | ( 0 ) -- - ( 1 ) ; Number of colors ; Initialize all color values as 0. This initialization is needed correct functioning of isSafe ( )
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V  4 NEW_LINE void printSolution ( int color [ ] ) ; void printSolution ( int color [ ] ) { cout << " Solution ▁ Exists : " " ▁ Following ▁ are ▁ the ▁ assigned ▁ colors ▁ STRNEWLINE " ; for ( int i = 0 ; i < V ; i ++ ) cout << " ▁ " << color [ i ] ; cout << " STRNEWLINE " ; } bool isSafe ( bool graph [ V ] [ V ] , int color [ ] ) { for ( int i = 0 ; i < V ; i ++ ) for ( int j = i + 1 ; j < V ; j ++ ) if ( graph [ i ] [ j ] && color [ j ] == color [ i ] ) return false ; return true ; } bool graphColoring ( bool graph [ V ] [ V ] , int m , int i , int color [ V ] ) { if ( i == V ) { if ( isSafe ( graph , color ) ) { printSolution ( color ) ; return true ; } return false ; } for ( int j = 1 ; j <= m ; j ++ ) { color [ i ] = j ; if ( graphColoring ( graph , m , i + 1 , color ) ) return true ; color [ i ] = 0 ; } return false ; } int main ( ) { bool graph [ V ] [ V ] = { { 0 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 } , { 1 , 1 , 0 , 1 } , { 1 , 0 , 1 , 0 } , } ; int m = 3 ; int color [ V ] ; for ( int i = 0 ; i < V ; i ++ ) color [ i ] = 0 ; if ( ! graphColoring ( graph , m , 0 , color ) ) cout << " Solution ▁ does ▁ not ▁ exist " ; return 0 ; }