30.8 Vertex coloring: greedy and DSATUR¶
Part 4 · Heuristic algorithms · Chapter 30 · Chapter 30: Constructive heuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt
- The problem of this section is the vertex coloring problem (VCP): its definition and its assumptions are on its page. The graph is \(G=(V,E)\), and the optimal value is the chromatic number \(\chi(G)\).
30.8.1 The greedy coloring¶
The Greedy Coloring Algorithm (denoted by \(GC\)) is a constructive heuristic for the VCP. The colors are the integers \(1,2,3,\dots\); the algorithm examines the vertices in the order of a given list \(\lambda\) and gives each vertex the smallest color not used by its neighbours already colored.
Algorithm: Greedy Coloring
-
The color classes \(Q_c=\{v : col[v]=c\}\) are independent sets by construction, so \(GC\) always returns a feasible coloring. It runs in \(O(n+|E|)\) time.
-
As \(LIST\), \(GC\) depends on the order of the list, and the order can make a large difference.
Example 30.12: \(GC\) on the Petersen graph, two orders
List \(\lambda=(1,2,\dots,10)\). The colors of the colored neighbours \(U\) and the color assigned are:
\(GC\) uses \(3\) colors (red \(=1\), blue \(=2\), yellow \(=3\) in the figure). The outer \(5\)-cycle \(1,2,3,4,5\) is an odd cycle and needs \(3\) colors, so \(\chi(G)=3\) and this coloring is optimal.
List \(\lambda=(1,2,3,4,5,7,8,6,9,10)\). The first five vertices get the same colors as before; then
and \(GC\) uses \(4\) colors: vertex \(8\) takes color \(2\), which the first order gave to vertex \(6\), and vertices \(9\) and \(10\) then see all three colors among their neighbours.
30.8.2 DSATUR¶
The DSATUR Algorithm (Degree of SATURation, denoted by \(DSATUR\)) is a constructive heuristic for the VCP. It does not use a fixed list: at each step it colors, with the smallest free color, an uncolored vertex of maximum saturation degree, i.e., with the largest number of different colors among its neighbours; ties are broken by the largest degree in the subgraph of the uncolored vertices, and then by the smallest index.
Algorithm: DSATUR
-
Why the saturation degree. A vertex with many different colors around it has few colors left: if we postpone it, it may end up with none of the colors already in use. \(DSATUR\) colors first the vertices that are most constrained, the same idea as “the hardest items first” of FFD and \(LPT\), but updated dynamically after each assignment.
-
\(DSATUR\) is \(GC\) with a list built on the fly, so every property of \(GC\) that holds for every list holds for \(DSATUR\) too. A straightforward implementation runs in \(O(n^2)\) time.
Example 30.13: \(DSATUR\) on the Petersen graph
All the vertices have degree \(3\). The vertex chosen at each step, its saturation degree, its degree among the uncolored vertices and its color are:
| step | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(v\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(8\) | \(7\) | \(9\) | \(10\) |
| \(sat[v]\) | \(0\) | \(1\) | \(1\) | \(1\) | \(2\) | \(1\) | \(2\) | \(1\) | \(2\) | \(2\) |
| \(du[v]\) | \(3\) | \(2\) | \(2\) | \(2\) | \(1\) | \(2\) | \(1\) | \(2\) | \(0\) | \(0\) |
| \(col[v]\) | \(1\) | \(2\) | \(1\) | \(2\) | \(3\) | \(2\) | \(3\) | \(1\) | \(3\) | \(2\) |
At step \(1\) all the vertices tie and vertex \(1\) is chosen. At step \(2\) the vertices \(2\), \(5\), \(6\) have saturation degree \(1\) and two uncolored neighbours each: the smallest index, \(2\), is chosen. At step \(7\) vertex \(8\) (neighbours \(3\) and \(6\), colors \(1\) and \(2\)) has saturation degree \(2\) and goes before vertex \(7\). \(DSATUR\) uses \(3=\chi(G)\) colors, the same coloring as \(GC\) with the list \((1,2,\dots,10)\).
30.8.3 What the greedy coloring guarantees¶
Proposition 30.5
For every graph \(G\) and every list \(\lambda\),
Proof
When vertex \(v\) is colored, the set \(U\) of the colors of its colored neighbours has at most \(\deg(v)\le\Delta(G)\) elements, so one of the colors \(1,2,\dots,\Delta(G)+1\) is not in \(U\), and the smallest free color is at most \(\Delta(G)+1\). □
-
The bound holds for \(DSATUR\) too, which is \(GC\) with a particular list, and it is attained by complete graphs (\(\Delta=n-1\), \(\chi=n\)) and odd cycles (\(\Delta=2\), \(\chi=3\)), whatever the list.
-
It is not a performance guarantee: it compares \(GC(I)\) with \(\Delta(G)+1\), not with \(\chi(G)\), and \(\Delta(G)+1\) can be much larger than \(\chi(G)\). The next proposition shows that a bad list can really force that many colors on a graph that needs only two.
-
On the other hand, some list is always optimal: if \(Q_1,\dots,Q_{\chi(G)}\) are the color classes of an optimal coloring, \(GC\) with the vertices of \(Q_1\) first, then those of \(Q_2\), and so on, gives each vertex of \(Q_c\) a color at most \(c\), so it uses at most \(\chi(G)\) colors. The difficulty is entirely in finding the list.
Proposition 30.6
For every \(k\ge3\) there is a graph \(G_k\) with \(n=2k\) vertices, \(\chi(G_k)=2\) and \(\Delta(G_k)=k-1\), and a list \(\lambda\), such that
Proof
\(G_k\) is the crown graph: the vertices are \(u_1,\dots,u_k\) and \(v_1,\dots,v_k\), and \(u_i\) is adjacent to \(v_j\) if and only if \(i\neq j\) (the complete bipartite graph \(K_{k,k}\) without a perfect matching). It is bipartite, with an edge, so \(\chi(G_k)=2\); every vertex has degree \(k-1\). The list is \(\lambda=(u_1,v_1,u_2,v_2,\dots,u_k,v_k)\).
We show by induction on \(i\) that \(GC\) gives color \(i\) to both \(u_i\) and \(v_i\). For \(i=1\) no neighbour is colored when \(u_1\) is examined, and \(v_1\) is not adjacent to \(u_1\): both get color \(1\). When \(u_i\) is examined, its colored neighbours are \(v_1,\dots,v_{i-1}\), with colors \(1,\dots,i-1\) by induction, so \(u_i\) gets color \(i\); when \(v_i\) is examined, its colored neighbours are \(u_1,\dots,u_{i-1}\) (\(u_i\) is not a neighbour), with colors \(1,\dots,i-1\), so \(v_i\) gets color \(i\) too. Hence \(GC(I_k)=k\). □
-
On the crown graphs \(\frac{GC(I_k)}{\chi(G_k)}=\frac{k}{2}=\frac{n}{4}\), which grows without bound: with an arbitrary list, \(GC\) has no constant performance guarantee. The list \((u_1,\dots,u_k,v_1,\dots,v_k)\), the color classes first, gives \(2\) colors.
-
The crown graphs satisfy the assumptions of the VCP for \(k\ge3\): no isolated vertices, and \(N(u_i)=\{v_j:j\neq i\}\) is not contained in \(N(u_{i'})\) nor in any \(N(v_j)\subseteq\{u_1,\dots,u_k\}\).
Example 30.14: \(GC\) and \(DSATUR\) on the crown graph \(G_4\)
Number the vertices \(u_i=2i-1\) and \(v_i=2i\), so that \(u_1,v_1,\dots,u_4,v_4\) are \(1,2,\dots,8\), and \(E=\{\{2i-1,2j\}: i\neq j\}\), with \(12\) edges.
With the list \((1,2,\dots,8)=(u_1,v_1,\dots,u_4,v_4)\), \(GC\) uses \(4\) colors, one for each pair \(\{u_i,v_i\}\) (shown in the figure); with the list \((1,3,5,7,2,4,6,8)\) it uses \(2\) colors.
\(DSATUR\) chooses vertex \(1\) (\(u_1\), color \(1\)), then the vertices \(4\), \(5\), \(2\), \(3\), \(6\), \(7\), \(8\), with colors \(2,1,2,1,2,1,2\): the vertices \(u_i\) get color \(1\) and the vertices \(v_i\) color \(2\), and \(DSATUR\) uses \(2=\chi(G_4)\) colors. After the first step, every vertex adjacent to a colored vertex has saturation degree \(1\), and the vertex chosen is always on the side opposite to the last one colored.
30.8.4 DSATUR as a heuristic¶
-
On bipartite graphs \(DSATUR\) always uses at most \(2\) colors, as on the crown graphs; this is proved in the paper that introduced it (Brélaz, 1979).
-
On general graphs \(DSATUR\) has no performance guarantee, since the VCP is not approximable. It is nevertheless one of the most used constructive heuristics for the VCP, because on most graphs it uses few colors more than \(\chi(G)\), often none; it is also the base of exact branch-and-bound algorithms for the VCP, which branch on the vertex chosen by the \(DSATUR\) rule.