Recently different approaches are developed to solve graph coloring - column generation method [ 1], genetic and Tabu search methods [ 2], branch and cut [ 3], evolutionary operators [ 4,7,8,10,11,13,14,15,16,1719,20], particle swarm optimization [ 5], backtracking [ 6,9], greedy and local search [ 12,18,21,22,23,24,25,26,27].

Graph coloring finds the least number of colors used to color the vertex set of a graph G [ 1,2,3,4,5]. Here the algorithm is developed for bipartite graph coloring. In a bipartite graph, the vertex set V(G) is split into two sets such that every vertex must be available in any one of the two sets. Clearly, the vertices in the same set are not connected by an edge. The bipartite graph and its partition are shown in figures 1 and 2.

The algorithm for bipartite graph coloring is defined as follows:

Traverse all vertices in G using the breadth-first search (BFS).

Choose a vertex and assign the color, say 1.

Assign the color 2 to all of its adjacent vertices.

Apply these steps until all vertices are assigned the colors.

The C++ implementation for bipartite graph coloring is given below:

Input n – number of vertices, e – number of edges.

Input all the edges.

Store the graph in adjacency list format.

Apply BFS using queue implementation and color V(G).

// Include header files bits/stdc++.h

int n, e, i, j;

vector<vector<int> > g;

vector<int> c;

bool v[ ];

void c(int nodes, int n) {

   queue<int> que;

   if(v[nodes]) return;

   c[nodes]=n;

   v[nodes]=1;

   for(i=0; i<n; i++) {

      if(!v[g[nodes][i]]) {

         q.push(g[nodes][i]);

&#x000a0; &#x000a0; &#x000a0; }

&#x000a0; &#x000a0;}

   while(!q.empty()) {

      c(q.front(), (n+1)%2);

      q.pop();

&#x000a0; &#x000a0;}

   return;

}

int main() {

   int a,b;

   cout<<"Enter n &#x00026; e";

   cin>>n>>e;

   g.resize(n);

   color.resize(n);

   memset(v,0,sizeof(v));

   for(i=0;i<e;i++) {

      cout<<"\nEnter edge vertices of edge "<<i+1<<" :";

      cin>>a>>b;

&#x000a0; &#x000a0; &#x000a0; a--; b--;

      g[a].push_back(b);

      g[b].push_back(a);

&#x000a0; &#x000a0;}

   c(0,1);

   for(i=0;i<n;i++) {

      if(color[i])

         cout<<i+1<<" "<<'1'<<"\n";

      else

cout<<i+1<<" "<<'2'<<"\n";

}

}

Enter n &#x00026; e:4 3

Color assignments: 1 2

Enter edges:

1 2

3 2

4 2

Colors:

1 1

2 2

3 2

4 2

The graph coloring algorithm is developed to solve bipartite graphs. The algorithm is executed on sample graphs and the results are obtained. In the future, different soft computing, hybrid strategies [ 28,29,30,31,32,33,34,35,36,37,38,39], and recommender systems with new strategies [ 40,41,42,43,44,45,46,47,48,49,50] can be applied to find minimal coloring with reduced complexity.