graphColouring.c

#include<stdio.h>
#include<conio.h>



static int m, n;
static int c=0;
static int count=0;
int g[50][50];
int x[50];



void nextValue(int k);
void GraphColoring(int k);



void main()

{

 int i, j;

 int temp;


 printf("\nEnter the number of vertex : " );

 scanf("%d", &n);





 printf("\nIs any edge present between them : \n");

 for(i=1; i<=n; i++)

 {

  x[i]=0;

  for(j=1; j<=n; j++)

  {

   if(i==j)

    g[i][j]=0;

   else

   {

    printf("vertex %d -> vertex %d : " , i, j);

    scanf("%d", &temp);

    g[i][j]=g[j][i]=temp;

   }

  }

 }








 printf("\nPossible Solutions are : \n");



 for(m=1;m<=n;m++)

 {

  if(c==1)

  {

   break;

  }

  GraphColoring(1);

 }



 printf("\nThe chromatic number is : %d", m-1);





 printf("\nThe total number of solutions is : %d", count);



 getch();

}





void GraphColoring(int k)

{

 int i;

 while(1)

 {

  nextValue(k);

  if(x[k]==0)

  {

   return;

  }



 if(k==n)

 {

  c=1;

  for(i=1;i<=n;i++)

  {
    if (x[i]==1)
    printf("R ");
    else if (x[i]==2)
    printf("G ");
    else
    printf("B ");

  }

  count++;

  printf("\n");

 }

 else

  GraphColoring(k+1);



 }

}





void nextValue(int k)

{

 int j;

 while(1)

 {

  x[k]=(x[k]+1)%(m+1);

  if(x[k]==0)

  {

   return;

  }

  for(j=1;j<=n;j++)

  {

   if(g[k][j]==1&&x[k]==x[j])

    break;

  }

  if(j==(n+1))

  {

   return;

  }

 }

}