Graph Coloring Technique

   GRAPH COLORING TECHNIQUE

DEFINATION:-

A coloring of a graph means assigning of a color to each vertex of the graph so that no two adjacent vertices are given the same color.In order to accomplish this we need the minimum number of colors to color the adjacent vertices which is called as the Chromatic Number of the graph.

PROCEDURE:-

Lets consider a un-directed graph G having V number of vertices and E number of  edges.

--> Enter the number of vertices of the graph.

--> Create an adjacency matrix of the above un-directed graph representing the             connected adjacent vertices.

  

--> Assign  Color 1 the nth vertices.

--> Check whether nth vertex is connected to any of previous (n-1) vertices 
      using  backtracking.

-->If connected then assign a color x[i]+1 where x[i] is the color of i th vertex          that is connected with nth vertex.

 SOURCE CODE USING C :-

#include<stdio.h>
#include<stdlib.h>

int col[100];
int adj[100][100];

void chkcolour(int v)
{
        int i;
        col[v]=1;
        for(i=0;i<v;i++)
        {
                if(adj[v][i]!=0 && col[v]==col[i])
                {
                        col[v]=col[i]+1;
                }
        }
}
void print_color(int v)
{
        int i;
        printf(" Printing the vertex colours:\n");
        for(i=0;i<v;i++)
        {
                 printf("Nodevertex-->[%d] has color --> :%d\n",i+1,col[i]);
        }

}

int main()
{
        int i,j,v;
        printf("enter the no of vertices:\n");
        scanf("%d",&v);
       printf("Start entering the values for adjacency matrix:\n");
        printf("________________________________________________\n");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        scanf("%d",&adj[i][j]);
                }
        }

        printf("_______________________________\n");

        printf("The entered adjacency matrix is:\n ");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        printf("%d",adj[i][j]);
                }
                printf("\n");
        }
        for(i=0;i<v;i++)
        {
                chkcolour(i);
        }
        chkcolour(v);
        printf("_______________________________\n");
        print_color(v);
        printf("_______________________________\n");


        return 0;
}



OUTPUT:

enter the no of vertices:
7
Start entering the values for adjacency matrix:
________________________________________________
0 1 1 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 1 0 1 1 0
1 0 1 1 0 1 0 
1 0 0 1 1 0 1
1 0 0 0 0 1 0
_______________________________
The entered adjacency matrix is:
 0110111
1010000
1101100
0010110
1011010
1001101
1000010
_______________________________
 Printing the vertex colours:
Nodevertex-->[1] has color --> :1
Nodevertex-->[2] has color --> :2
Nodevertex-->[3] has color --> :3
Nodevertex-->[4] has color --> :1
Nodevertex-->[5] has color --> :2
Nodevertex-->[6] has color --> :3
Nodevertex-->[7] has color --> :2

_______________________________

**********************************************************************************