Write (and test) a C program to edge color a provided bipartite graph. The input to your program will be: a. , , and m, the numbers of left column vertices, right column vertices, and edges. and . b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur. The output from your program will be: a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (a, b) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path. b. A list of the edges (input order) and the final color for each edge. 2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu. Getting Started: 1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1). 2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D. 3. Do not use backtracking instead of the alternating (a, b) path technique. 4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.

 Write (and test) a C program to edge color a provided bipartite graph.

The input to your program will be:
a. , , and m, the numbers of left column vertices, right column vertices, and edges. and .
b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur.
The output from your program will be:
a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (a, b) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path.
b. A list of the edges (input order) and the final color for each edge.
2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu.
Getting Started:
1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1).
2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D.
3. Do not use backtracking instead of the alternating (a, b) path technique.
4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.

#include<stdio.h>
#include<stdlib.h>
//return 1 if two colors are sufficient. O not.
int canColorTwo(int vertices, int **graph){
int i,j;
//res will stores the i th vertex assigned color.
int *res = (int *)malloc(sizeof(int)*vertices);
//color will stres the i th color avilable or not.available means
0.otherwise 1.
int *color = (int *)malloc(sizeof(int)*vertices);
for(i 0;i<vertices;i++){
res[i] = -1;
color[i] = 0;

}
res[0] = 0;
//for each vertex in graph.
for(i =1;i<vertices; i++){
//making the colour to neighbour vertices as unavilable.

for(j =0;j<vertices;j++) {

if(graph[i][j] == 1&& res[j] ! = -1) {

color[res[j]] = 1;

}

}

//finding color.

for(j =0;j<vertices;j++) {

if(color[j] == 0 ) break;

}

// assigning color.

res[i] = j;

// reseting the color for the next vertoces.

for(j =0;j<vertices;j++) {

if(graph[i][j] == 1 && res[j]! = -1) color[res[j]] = 0;

}

}

//finding the max color are required to color the graph.

int max = res[0];

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

if(max< res[i]) max = res[i];

}

//return

if(max<2) return 1;

return 0;

}

int main() {

//reading data.

int vertices,edges,i,j;

scanf("%d",&vertices);

scanf("%d",&edges);

//creating adjecency graph matrix.

int **graph = (int **)malloc(vertices*sizeof(int));

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

graph[i] = (int *)malloc(sizeof(int)&vertices);

}

//making all cells as -1. means no (vi,vi +1) connection.

for(i =0;i< vertices;i++)

for(j =0;j<vertices;j++)

graph[i][j] = -1;

//adding edjes in the graph.

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

int u,v;

scanf("%d%d",&u,&v);

graph[u][v] = 1;

graph[v][u] = 1;

}

//calling canColorTwo() if possible displaying two-color.otherwise no two-color.

if(canColorTwo(vertices,graph) == 1) {

printf("two-color");

}

else {

printf("no two-color");

}

return 0;

}