It is possible to represent a graph by bi-coloring if, every neighbor nodes color is different than itself.

We can use bfs or dfs for bicoloring. example is using dfs.

void BiColor(long node)
{
long i;

for(i=1;i<=n;i++)
if(A[node][i]==1)
{
if(color[i]==-1)
{
color[i] = (color[node] + 1 )%2;
BiColor(i);
}
else if(color[i]==color[node])
yes = 0;

if(yes==0)
break;
}
}

color[]={-1};

A[][] = connection matrix.

n = number of nodes, from 1 to n.
yes = 1;
for(i=1;i<=n;i++)
if(color[i]==-1)
{
color[i]=0;
BiColor(i);
}

if(yes==1)
printf(“possible\n”);
else
printf(“not possible\n”);

Advertisements