SOURCE CODE :
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
bool isSafe(int graph[MAX_VERTICES][MAX_VERTICES], int color[], int v, int c, int V) {
for (int i = 0; i < V; i++) {
if (graph[v][i] == 1 && color[i] == c) {
return false;
}
}
return true;
}
bool graphColoringUtil(int graph[MAX_VERTICES][MAX_VERTICES], int color[], int V, int m,
int v) {
if (v == V) {
return true;
}
for (int c = 1; c <= m; c++) {
if (isSafe(graph, color, v, c, V)) {
color[v] = c;
if (graphColoringUtil(graph, color, V, m, v + 1)) {
return true;
}
color[v] = 0;
}
}
return false;
}
bool graphColoring(int graph[MAX_VERTICES][MAX_VERTICES], int V, int m) {
int color[MAX_VERTICES];
for (int i = 0; i < V; i++) {
color[i] = 0;
}
if (graphColoringUtil(graph, color, V, m, 0)) {
printf("Solution exists: Coloring of the graph:\n");
for (int i = 0; i < V; i++) {
printf("Vertex %d -> Color %d\n", i, color[i]);
}
return true;
}
printf("Solution does not exist with %d colors.\n", m);
return false;
}
int main() {
int V, E, m;
printf("Enter the number of vertices: ");
scanf("%d", &V);
int graph[MAX_VERTICES][MAX_VERTICES] = {0};
printf("Enter the number of edges: ");
scanf("%d", &E);
printf("Enter the edges (u v) for each edge (0-based index):\n");
for (int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = 1;
graph[v][u] = 1;
}
printf("Enter the number of colors: ");
scanf("%d", &m);
if (!graphColoring(graph, V, m)) {
printf("Graph cannot be colored with %d colors.\n", m);
}
return 0;
}
OUTPUT :
