GRAPH COLOURING

//program to implement graph coloring problem
// graph nodes are from 0..n-1
// colors are from 1.. m

import java.io.*;
class   GraphColor
{
boolean adj[][];
int n;
GraphColor(){}

GraphColor(int k)
{
n=k;
adj=new boolean[n][n];
}

void   add(int a,int b)
{
adj[a][b]=adj[b][a]=true;
}
boolean colorCheck(int k,int x[])
{
int i;
for(i=0;i<n;++i)
if(x[i]==x[k]  &&adj[i][k])return false;
return true;
}

void mColoring(int m,int k,int x[])

{ int i,j;
for(i=1;i<=m;++i)
{
x[k]=i;
if(colorCheck(k,x))
if(k==n-1)
{
for(j=0;j<n;++j)
System.out.print(x[j]+” “);
System.out.println();
}
else mColoring(m,k+1,x);
}
x[k]=0;
}

public static void main(String args[])throws IOException
{
GraphColor g1;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int a,b,n,m,e;
System.out.println(“Enter no: of nodes and Edges”);
n=Integer.parseInt(br.readLine());
e=Integer.parseInt(br.readLine());
g1=new GraphColor(n);
for(int i=1;i<=e;++i)
{
System.out.println(“Enter an edge”);
a=Integer.parseInt(br.readLine());
b=Integer.parseInt(br.readLine());
g1.add(a,b);
}
System.out.println(“enter number of  colors”);
m=Integer.parseInt(br.readLine());
int x[]=new int[n];
g1.mColoring(m,0,x);
}
}