Algorithm Deep Dive: Graph Coloring Heuristics (Greedy, Welsh-Powell, DSatur)

A Bit of History

Greedy coloring is the natural first attempt at any coloring problem, but its weakness — extreme sensitivity to vertex order — motivated better orderings. In 1967, Dominic Welsh and Martin Powell published a simple but effective fix: sort vertices by descending degree before coloring greedily, guaranteeing a coloring using at most $\Delta + 1$ colors matching known upper bounds. Over a decade later, Daniel Brélaz introduced DSatur (Degree of Saturation) in his 1979 paper "New Methods to Color the Vertices of a Graph", replacing the static degree ordering with a dynamic one that adapts as coloring proceeds — DSatur remains one of the strongest general-purpose coloring heuristics in practical use today, over four decades later.

Greedy Coloring: Arbitrary Order

The simplest possible approach: process vertices in any fixed order (even arbitrary), and assign each vertex the lowest-numbered color not already used by any already-colored neighbor.

Guarantee & Weakness

Greedy coloring always uses at most $\Delta + 1$ colors, where $\Delta$ is the maximum degree — but the order of vertices dramatically affects the result. A poorly chosen order can force greedy coloring to use far more colors than the true chromatic number $\chi(G)$ requires; a well-chosen order can sometimes achieve the optimum. This sensitivity motivates the smarter orderings below.

Welsh-Powell: Degree-Descending Order

Sort all vertices once, by descending degree, before running the greedy pass. Intuition: high-degree vertices have the most constraints (most neighbors competing for colors), so coloring them first, while the fewest colors are already "used up," gives them the best chance of reusing an early color instead of forcing a brand-new one.

DSatur: Saturation Degree Order

Welsh-Powell's ordering is static — computed once, up front. DSatur instead recomputes the "most urgent" vertex to color at every step, using a value called saturation degree: the number of distinct colors already used among a vertex's neighbors (not just neighbor count).

At each step, pick the uncolored vertex with the highest saturation degree (most distinct neighbor colors already "blocking" it) — ties broken by highest remaining degree.
Assign it the lowest available color not used by any neighbor.
Update saturation degrees of its neighbors, and repeat.

Because saturation degree changes dynamically as coloring proceeds (a vertex becomes more constrained as more of its neighbors get colored), DSatur reacts to the evolving state of the coloring rather than committing to a fixed plan upfront — this adaptivity is why it consistently outperforms Welsh-Powell in practice, especially on graphs with irregular degree distributions.

Worked Example

Star-like graph: center vertex 0 connected to 1, 2, 3, 4; plus an extra edge 1-2.

Welsh-Powell order (by degree): vertex 0 (degree 4) first, then 1 and 2 (degree 2 each), then 3, 4 (degree 1 each). Color 0 = A. Color 1 = B (differs from 0). Color 2 = C (differs from 0 and 1, since 1-2 is an edge). Color 3 = B (only conflicts with 0). Color 4 = B. Total colors used: 3.
DSatur: initially all saturation degrees are 0 except by raw degree tie-break, so vertex 0 (degree 4) colored first: A. Now 1, 2, 3, 4 each have saturation degree 1 (one neighbor colored A) — tie, break by degree: 1 and 2 have degree 2 (due to the 1-2 edge), pick 1: color B. Now vertex 2 has saturation degree 2 (sees both A from vertex 0 and B from vertex 1) — highest priority: color C. Vertices 3, 4 have saturation degree 1: color B. Same result here (3 colors), but DSatur's dynamic re-evaluation would diverge from Welsh-Powell on more irregular graphs.

Complexity Analysis

Heuristic	Time Complexity	Color Guarantee
Greedy (arbitrary order)	$O(V + E)$	$\leq \Delta + 1$ colors
Welsh-Powell	$O(V \log V + E)$	$\leq \Delta + 1$ colors (often fewer in practice)
DSatur	$O(V^2)$ (naive) or $O((V+E)\log V)$ (with a priority queue)	Exact for bipartite & some structured classes; near-optimal in general

Implementation

def greedy_coloring(n, adj, order=None):
    """Colors vertices in the given order (or 0..n-1 if None)."""
    if order is None:
        order = list(range(n))

    color = [-1] * n
    for u in order:
        used = {color[v] for v in adj[u] if color[v] != -1}
        c = 0
        while c in used:
            c += 1
        color[u] = c
    return color

def welsh_powell_coloring(n, adj):
    """Sort vertices by descending degree, then greedy color."""
    order = sorted(range(n), key=lambda v: -len(adj[v]))
    return greedy_coloring(n, adj, order)

def dsatur_coloring(n, adj):
    """Dynamic saturation-degree based coloring."""
    color = [-1] * n
    degree = [len(adj[v]) for v in range(n)]
    saturation = [set() for _ in range(n)]  # distinct neighbor colors seen
    colored_count = 0

    while colored_count < n:
        # Pick uncolored vertex with max saturation, tie-break by degree
        best = -1
        for v in range(n):
            if color[v] == -1:
                if best == -1 or (len(saturation[v]), degree[v]) > (len(saturation[best]), degree[best]):
                    best = v

        used = saturation[best]
        c = 0
        while c in used:
            c += 1
        color[best] = c
        colored_count += 1

        for neighbor in adj[best]:
            if color[neighbor] == -1:
                saturation[neighbor].add(c)

    return color

# Example: star graph 0-1,0-2,0-3,0-4 plus edge 1-2
n = 5
adj = [[] for _ in range(n)]
for u, v in [(0,1),(0,2),(0,3),(0,4),(1,2)]:
    adj[u].append(v); adj[v].append(u)

print("Greedy (natural order):", greedy_coloring(n, adj))
print("Welsh-Powell:", welsh_powell_coloring(n, adj))
print("DSatur:", dsatur_coloring(n, adj))

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<int> greedyColoring(int n, vector<vector<int>>& adj, vector<int> order) {
    vector<int> color(n, -1);
    for (int u : order) {
        set<int> used;
        for (int v : adj[u]) if (color[v] != -1) used.insert(color[v]);
        int c = 0;
        while (used.count(c)) c++;
        color[u] = c;
    }
    return color;
}

vector<int> welshPowellColoring(int n, vector<vector<int>>& adj) {
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) {
        return adj[a].size() > adj[b].size();
    });
    return greedyColoring(n, adj, order);
}

vector<int> dsaturColoring(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);
    vector<set<int>> saturation(n);
    int coloredCount = 0;

    while (coloredCount < n) {
        int best = -1;
        for (int v = 0; v < n; v++) {
            if (color[v] == -1) {
                if (best == -1 ||
                    make_pair(saturation[v].size(), adj[v].size()) >
                    make_pair(saturation[best].size(), adj[best].size())) {
                    best = v;
                }
            }
        }

        int c = 0;
        while (saturation[best].count(c)) c++;
        color[best] = c;
        coloredCount++;

        for (int nb : adj[best]) {
            if (color[nb] == -1) saturation[nb].insert(c);
        }
    }
    return color;
}

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    for (auto& e : vector<pair<int,int>>{{0,1},{0,2},{0,3},{0,4},{1,2}}) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    auto wp = welshPowellColoring(n, adj);
    cout << "Welsh-Powell: ";
    for (int c : wp) cout << c << " ";
    cout << endl;

    auto ds = dsaturColoring(n, adj);
    cout << "DSatur: ";
    for (int c : ds) cout << c << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class ColoringHeuristics {
    static int[] greedyColoring(int n, List<List<Integer>> adj, List<Integer> order) {
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int u : order) {
            Set<Integer> used = new HashSet<>();
            for (int v : adj.get(u)) if (color[v] != -1) used.add(color[v]);
            int c = 0;
            while (used.contains(c)) c++;
            color[u] = c;
        }
        return color;
    }

    static int[] welshPowellColoring(int n, List<List<Integer>> adj) {
        List<Integer> order = new ArrayList<>();
        for (int i = 0; i < n; i++) order.add(i);
        order.sort((a, b) -> adj.get(b).size() - adj.get(a).size());
        return greedyColoring(n, adj, order);
    }

    static int[] dsaturColoring(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Arrays.fill(color, -1);
        List<Set<Integer>> saturation = new ArrayList<>();
        for (int i = 0; i < n; i++) saturation.add(new HashSet<>());
        int coloredCount = 0;

        while (coloredCount < n) {
            int best = -1;
            for (int v = 0; v < n; v++) {
                if (color[v] == -1) {
                    if (best == -1 ||
                        saturation.get(v).size() > saturation.get(best).size() ||
                        (saturation.get(v).size() == saturation.get(best).size() &&
                         adj.get(v).size() > adj.get(best).size())) {
                        best = v;
                    }
                }
            }

            int c = 0;
            while (saturation.get(best).contains(c)) c++;
            color[best] = c;
            coloredCount++;

            for (int nb : adj.get(best)) {
                if (color[nb] == -1) saturation.get(nb).add(c);
            }
        }
        return color;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{0,2},{0,3},{0,4},{1,2}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        System.out.println("Welsh-Powell: " + Arrays.toString(welshPowellColoring(n, adj)));
        System.out.println("DSatur: " + Arrays.toString(dsaturColoring(n, adj)));
    }
}

Real-World Applications

Case Study

Register Allocation & Exam Timetabling

Compilers use graph coloring heuristics (typically Chaitin's algorithm, a variant built on greedy/DSatur ideas) to assign a limited number of physical CPU registers to a much larger set of program variables, treating variables that are "live" simultaneously as conflicting (adjacent) in an interference graph. Universities use these same heuristics to schedule exams: courses sharing students become adjacent vertices, and each color represents a distinct exam time slot, minimizing scheduling conflicts.

Compiler DesignScheduling

Exercises

Construct a graph where a poor greedy vertex ordering uses far more colors than the chromatic number, while a good ordering achieves the optimum.
Run DSatur and Welsh-Powell on the Petersen graph and compare the number of colors each produces.
Prove that DSatur always finds the exact chromatic number on bipartite graphs.
Challenge: Implement recursive largest first (RLF), another classical coloring heuristic, and compare its results against DSatur on a random graph benchmark.

Limitations

No Optimality Guarantee

None of these heuristics guarantee an optimal (minimum-color) coloring — they are polynomial-time approximations to an NP-hard problem. For applications requiring a provably minimum coloring, exact methods (backtracking, SAT-based, or ILP formulations) remain necessary, trading exponential worst-case time for a correctness guarantee.

Cookie Consent

Graph Coloring Heuristics

Contents

A Bit of History

Greedy Coloring: Arbitrary Order

Guarantee & Weakness

Welsh-Powell: Degree-Descending Order

DSatur: Saturation Degree Order

Worked Example

Complexity Analysis

Implementation

Real-World Applications

Register Allocation & Exam Timetabling

Exercises

Limitations

No Optimality Guarantee

Cookie Consent

Graph Coloring Heuristics

Contents

A Bit of History

Greedy Coloring: Arbitrary Order

Guarantee & Weakness

Welsh-Powell: Degree-Descending Order

DSatur: Saturation Degree Order

Worked Example

Complexity Analysis

Implementation

Real-World Applications

Register Allocation & Exam Timetabling

Exercises

Limitations

No Optimality Guarantee

Related Deep Dives

Graph Theory Series

Bipartite Testing & k-Colorability Backtracking

Part 13: Graph Coloring