Let G be a graph and m be a given positive integer. We want to whether the nodes of G can be colored in such a way that no two adjacent nodes have the same color yet only m colors are used.

Example:
Let graph G has 5 nodes (a, b, c, d, e) and adjacent matrix is as follows-
* a b c d e
a 0 1 1 0 1
b 1 0 1 0 1
c 1 1 0 1 0
d 0 0 1 0 1
e 1 1 0 1 0

Answer:
Vertex a is color 1
Vertex b is color 2
Vertex c is color 3
Vertex d is color 1
Vertex e is color 3

I have solve this problem in c programming and it run properly in Cygwin.





#include
const int MAX = 100;
// a[i][j] = 0 if i-th and j-th vertices are not adjacent
int a[100][100];
// color[i] = 1 if we have colored
int color[100];
// array degree[n] stores the degrees of the vertices
int degree[100];
// array NN[] stores all the vertices that is not adjacent to current vertex
int NN[100];
//n is the number of vertex
int n;
// NNCount is the number of that set
int NNCount;
// unprocessed is the number of vertices with which we 've not worked
int unprocessed;

//input function
void GetInput(){
 int i, j;
 printf("Enter the number of row or colum: ");
 scanf("%d", &n);
 for (i=0; imax)
   {
    max = degree[i];
    max_i = i;
   }
 return max_i;
}


// it reset the value of scanned array
void scannedInit(int scanned[MAX]){
 int i;
 for (i=0; i VerticesInCommon){
    VerticesInCommon = temp;
    y = tmp_y;
   }
  }
 return y;
}

// find the vertex in NN of which degree is maximum
int MaxDegreeInNN(){
 int tmp_y, i, j;
 int temp, max = 0;
 for (i=0; imax){
   max = temp;
   tmp_y = NN[i];
  }
 }
 return tmp_y;
}

// processing function
void Coloring(){
 int x,y;
 int ColorNumber = 0;
 int VerticesInCommon = 0;
 while (unprocessed>0){
  x = MaxDegreeVertex();
  ColorNumber ++;
  color[x] = ColorNumber;
  unprocessed --;
  UpdateNN(ColorNumber);
  while (NNCount>0){
  y = FindSuitableY(ColorNumber, VerticesInCommon);
  if (VerticesInCommon == 0)
  y = MaxDegreeInNN();
  color[y] = ColorNumber;
  unprocessed --;
  UpdateNN(ColorNumber);
  }
 }
}

// print out the output
void PrintOutput(){
 int i;
 for ( i=0; i < n; i++)
  printf("Vertex %d is colored %d \n", i+1, color[i] );
}

// main function
int main(){
 GetInput();
 Init();
 Coloring();
 PrintOutput();
}