Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.
import java.io.*;
class GraphColor {
int g[][], n, m, e;
int x[];
void read() throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println("How many vertices and edges..");
n = Integer.parseInt( in .readLine());
g = new int[n + 1][n + 1];
x = new int[n + 1];
e = Integer.parseInt( in .readLine());
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = 0;
for (int i = 1; i <= e; i++) {
System.out.println("Enter end vertices...");
int a = Integer.parseInt( in .readLine());
int b = Integer.parseInt( in .readLine());
g[a][b] = g[b][a] = 1;
}
System.out.println("How many colors...");
m = Integer.parseInt( in .readLine());
}
void mColoring(int k) {
do {
nextValue(k);
if (x[k] == 0)
break;
if (k == n) {
for (int i = 1; i <= k; i++)
System.out.print(x[i] + " ");
System.out.println();
} else
mColoring(k + 1);
}
while (true);
}
void nextValue(int k) {
int j;
do {
x[k] = (x[k] + 1) % (m + 1);
if (x[k] == 0)
break;
for (j = 1; j <= n; j++) {
if (g[k][j] != 0 && x[j] == x[k])
break;
}
if (j == n + 1)
break;
}
while (true);
}
}
class TestGraphColor {
public static void main(String args[]) throws IOException {
GraphColor ob = new GraphColor();
ob.read();
ob.mColoring(1);
}
}
/*
How many vertices and edges..
6
8
Enter end vertices...
1
2
Enter end vertices...
1
3
Enter end vertices...
2
3
Enter end vertices...
2
4
Enter end vertices...
3
5
Enter end vertices...
4
5
Enter end vertices...
4
6
Enter end vertices...
5
6
How many colors...
3
1 2 3 1 2 3
1 2 3 3 1 2
1 2 3 3 2 1
1 3 2 1 3 2
1 3 2 2 1 3
1 3 2 2 3 1
2 1 3 2 1 3
2 1 3 3 1 2
2 1 3 3 2 1
2 3 1 1 2 3
2 3 1 1 3 2
2 3 1 2 3 1
3 1 2 2 1 3
3 1 2 2 3 1
3 1 2 3 1 2
3 2 1 1 2 3
3 2 1 1 3 2
3 2 1 3 2 1
Process Exit...
*/