📚 DAA Tutorial

Design and Analysis of Algorithms

Learn Design and Analysis of Algorithms concepts with simple explanations, algorithms, examples and practical notes.

← Back to DAA

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 m=d+1.

abecd 12331
Colors shown beside each node. Chromatic number = 3.

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.

12345
The graph corresponding to a map with 5 regions. This map requires 4 colors.

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 (x1,…,xn) where xi 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 xi, 1 ≤ i ≤ n. Nodes at level n + 1 are leaf nodes.

State space tree when n = 3 and m = 3

x₁=1112321233123x₁=2112321233123x₁=3112321233123x₁x₂x₃

Each path to a leaf represents a coloring using at most three colors. Only 12 solutions exist with 3 colors.

Computing time: O(nmn).

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

x[k]=(x[k]+1)mod(m+1)

Example: a 4-node graph and all 3-colorings

1234

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.

x₁=1212332312323x₁=2121331313213x₁=3121312212312x₁x₂x₃x₄

N-Queens: number of solutions

N-Queen boardTotal solutionsUnique solutions
1 × 111
2 × 200
3 × 300
4 × 421
5 × 5102
6 × 641
7 × 7406
8 × 89212
9 × 935246
10 × 1072492

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):

G=[ 0101 1010 0101 1010 ]

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 (x1,x2,x3,x4)=(0,0,0,0).

mColoring(1): NextValue(1)

k = 1: x[1] = (0 + 1) mod (3 + 1) = 1 mod 4 = 1.

jG[1, j] ≠ 0x[1] = x[j]Outcome
10 ≠ 0, F–continue
21 ≠ 0, T1 = 0, Fcontinue
30 ≠ 0, F–continue
41 ≠ 0, T1 = 0, Fcontinue
55 = 4 + 1return; x[1] = 1

mColoring(2): NextValue(2)

k = 2: x[2] = (0 + 1) mod 4 = 1.

jG[2, j] ≠ 0x[2] = x[j]Outcome
11 ≠ 0, T1 = 1, Tbreak (color 1 rejected; j = 2, 3, 4 not examined)

Next, x[2] = 2 mod 4 = 2.

jG[2, j] ≠ 0x[2] = x[j]Outcome
11 ≠ 0, T2 = 1, Fcontinue
20 ≠ 0, F–continue
31 ≠ 0, T2 = 0, Fcontinue
40 ≠ 0, F–continue
5j = n + 1return; x[2] = 2

mColoring(3): NextValue(3)

k = 3: x[3] = 1.

jG[3, j] ≠ 0x[3] = x[j]Outcome
10 ≠ 0, F–continue
21 ≠ 0, T1 = 2, Fcontinue
30 ≠ 0, F–continue
41 ≠ 0, T1 = 0, Fcontinue
5j = n + 1return; x[3] = 1

mColoring(4): NextValue(4)

k = 4: x[4] = 1.

jG[4, j] ≠ 0x[4] = x[j]Outcome
11 ≠ 0, T1 = 1, Tbreak (color 1 rejected; j = 2, 3, 4 not examined)

Next, x[4] = 2.

jG[4, j] ≠ 0x[4] = x[j]Outcome
11 ≠ 0, T2 = 1, Fcontinue
20 ≠ 0, F–continue
31 ≠ 0, T2 = 1, Fcontinue
40 ≠ 0, F–continue
5j = n + 1return; x[4] = 2

Since k = 4 = n, the algorithm writes (x1,x2,x3,x4)=(1,2,1,2).