Graph Coloring
Let G be a graph and m be a given positive number. Discover whether the nodes of G can be colored in such a way that no two adjacent nodes have the same color, yet only m colors are used. This is called the m-colorability decision problem. The smallest such m is called the chromatic number.
If d is the degree of the given graph, then it can be colored with d + 1 colors; here .
Planar graphs and maps
A graph is said to be planar if and only if it can be drawn in a plane in such a way that no two edges cross each other. A famous special case of the m-colorability decision problem is the 4-color problem for planar graphs.
Any map can be easily transformed into a graph. Each region of the map becomes a node, and if two regions are adjacent then the corresponding nodes are joined by an edge.
The sketch of the map itself (five regions drawn as nested boxes) is not redrawn here; only its graph is.
For any size of map, five colors are sufficient.
Representation
Suppose we represent a graph by its adjacency matrix G[1:n, 1:n], where G[i, j] = 1 if (i, j) is an edge of G and G[i, j] = 0 otherwise.
The colors can be represented by the integers 1, 2, …, m, and solutions are given by the tuple where is the color of node i.
Algorithm mColoring(k)
Algorithm mColoring(k)
/* This algorithm was formed using the recursive backtracking schema.
The graph is represented by its boolean adjacency matrix G[1:n, 1:n].
All assignments of 1, 2, ..., m to the vertices of the graph such that
adjacent vertices are assigned distinct integers are printed.
k is the index of the next vertex to color. */
{
repeat
{ // Generate all legal assignments for x[k].
NextValue(k); // Assign to x[k] a legal color.
if (x[k] = 0) then return; // No new color possible
if (k = n) then // At most m colors have been used
write(x[1:n]); // to color the n vertices.
else mColoring(k + 1);
} until (false);
}
The underlying state space tree is a tree of degree m and height n + 1. Each node at level i has m children corresponding to the m possible assignments to , 1 ≤ i ≤ n. Nodes at level n + 1 are leaf nodes.
State space tree when n = 3 and m = 3
Each path to a leaf represents a coloring using at most three colors. Only 12 solutions exist with 3 colors.
Computing time: .
Algorithm NextValue(k)
Algorithm NextValue(k)
/* x[1], ..., x[k-1] have been assigned integer values in the range [1, m]
such that adjacent vertices have distinct integers. A value for x[k]
is determined in the range [0, m]. x[k] is assigned the next highest
numbered color while maintaining distinctness from the adjacent
vertices of vertex k. If no such color exists, then x[k] is 0. */
{
repeat
{
x[k] := (x[k] + 1) mod (m + 1); // Next highest color
if (x[k] = 0) then return; // All colors have been used
for j := 1 to n do
{ // Check if this color is distinct from adjacent colors
if ((G[k, j] ≠ 0) and (x[k] = x[j]))
// i.e. (k, j) is an edge and the adjacent vertices have the same color
then break;
}
if (j = n + 1) then return; // New color found
} until (false);
}
The color update is the formula
Example: a 4-node graph and all 3-colorings
A 4-node graph and all possible 3-colorings. Only legal partial colorings are shown, so the tree has 18 leaves, one for each way to 3-color the graph.
N-Queens: number of solutions
| N-Queen board | Total solutions | Unique solutions |
|---|---|---|
| 1 × 1 | 1 | 1 |
| 2 × 2 | 0 | 0 |
| 3 × 3 | 0 | 0 |
| 4 × 4 | 2 | 1 |
| 5 × 5 | 10 | 2 |
| 6 × 6 | 4 | 1 |
| 7 × 7 | 40 | 6 |
| 8 × 8 | 92 | 12 |
| 9 × 9 | 352 | 46 |
| 10 × 10 | 724 | 92 |
The notes show 362 for the 9 × 9 total; the known value is 352, which is used here.
Trace of mColoring(1), n = 4, m = 3
Graph: the 4-cycle above, with adjacency matrix G (rows and columns 1 to 4):
In the handwritten matrix, rows 3 and 4 leave out the edge (3, 4); it is included here so that the matrix matches the graph. The trace results are the same either way.
Initially .
mColoring(1): NextValue(1)
k = 1: x[1] = (0 + 1) mod (3 + 1) = 1 mod 4 = 1.
| j | G[1, j] ≠ 0 | x[1] = x[j] | Outcome |
|---|---|---|---|
| 1 | 0 ≠ 0, F | – | continue |
| 2 | 1 ≠ 0, T | 1 = 0, F | continue |
| 3 | 0 ≠ 0, F | – | continue |
| 4 | 1 ≠ 0, T | 1 = 0, F | continue |
| 5 | 5 = 4 + 1 | return; x[1] = 1 | |
mColoring(2): NextValue(2)
k = 2: x[2] = (0 + 1) mod 4 = 1.
| j | G[2, j] ≠ 0 | x[2] = x[j] | Outcome |
|---|---|---|---|
| 1 | 1 ≠ 0, T | 1 = 1, T | break (color 1 rejected; j = 2, 3, 4 not examined) |
Next, x[2] = 2 mod 4 = 2.
| j | G[2, j] ≠ 0 | x[2] = x[j] | Outcome |
|---|---|---|---|
| 1 | 1 ≠ 0, T | 2 = 1, F | continue |
| 2 | 0 ≠ 0, F | – | continue |
| 3 | 1 ≠ 0, T | 2 = 0, F | continue |
| 4 | 0 ≠ 0, F | – | continue |
| 5 | j = n + 1 | return; x[2] = 2 | |
mColoring(3): NextValue(3)
k = 3: x[3] = 1.
| j | G[3, j] ≠ 0 | x[3] = x[j] | Outcome |
|---|---|---|---|
| 1 | 0 ≠ 0, F | – | continue |
| 2 | 1 ≠ 0, T | 1 = 2, F | continue |
| 3 | 0 ≠ 0, F | – | continue |
| 4 | 1 ≠ 0, T | 1 = 0, F | continue |
| 5 | j = n + 1 | return; x[3] = 1 | |
mColoring(4): NextValue(4)
k = 4: x[4] = 1.
| j | G[4, j] ≠ 0 | x[4] = x[j] | Outcome |
|---|---|---|---|
| 1 | 1 ≠ 0, T | 1 = 1, T | break (color 1 rejected; j = 2, 3, 4 not examined) |
Next, x[4] = 2.
| j | G[4, j] ≠ 0 | x[4] = x[j] | Outcome |
|---|---|---|---|
| 1 | 1 ≠ 0, T | 2 = 1, F | continue |
| 2 | 0 ≠ 0, F | – | continue |
| 3 | 1 ≠ 0, T | 2 = 1, F | continue |
| 4 | 0 ≠ 0, F | – | continue |
| 5 | j = n + 1 | return; x[4] = 2 | |
Since k = 4 = n, the algorithm writes .