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

A Short History of Coloring Heuristics

Graph coloring grew from a mathematical puzzle into a practical language for timetabling, resource assignment, and constraint processing. The heuristics in this article share one lineage: keep the fast first-fit rule, but become increasingly deliberate about which vertex is colored next.

1852

Francis Guthrie's map-coloring question helped launch the subject: how few colors ensure neighboring regions differ?

1967

Dominic Welsh and Martin Powell connected coloring directly to timetabling and proposed a degree-based construction together with a computable upper bound.

1979

Daniel Brélaz introduced DSATUR, replacing a once-only ordering with a priority that changes after every color assignment.

Today

Constructive heuristics supply fast feasible solutions and upper bounds; exact solvers reuse their colorings to prune backtracking, SAT, or integer-programming search.

Primary sources: Welsh–Powell (1967) and Brélaz (1979).

The Shared Greedy Core

All three methods eventually perform the same local move: assign the smallest nonnegative color absent from the already-colored neighborhood. They differ only in the policy that supplies the next vertex.

Always feasible

On a loop-free graph, first-fit always finds some color. The output can be verified by checking $c(u)\ne c(v)$ for every edge.

An upper bound, not a proof of optimality

If the heuristic uses $q$ colors, then $\chi(G)\leq q$. It does not prove that $q$ is the smallest possible value.

A coloring heuristic separates selection from assignment. That separation makes implementations easier to compare and lets exact solvers reuse the heuristic as an upper-bound routine.

Greedy Coloring: Arbitrary Order

Given an order $v_1,v_2,\ldots,v_n$, process one vertex at a time. When coloring $v_i$, look only at its already-colored neighbors and choose the smallest available color. Later vertices must adapt to earlier decisions; greedy never revisits a color once assigned.

Read the next vertex

The order may come from input, arrival time, a randomized shuffle, or another heuristic.

Mark forbidden colors

Collect the colors used by neighbors that have already been processed. Uncolored neighbors impose no restriction yet.

Choose first-fit

Assign the smallest color not in the forbidden set. A vertex of degree $d$ can forbid at most $d$ colors.

Why the $\Delta+1$ Bound Is Immediate

A vertex has at most $\Delta$ neighbors, so at most $\Delta$ distinct colors can be blocked when it is processed. Among colors $0,1,\ldots,\Delta$, at least one remains available.

Why Order Matters: One Graph, Two Outcomes

Consider the crown graph $K_{4,4}$ with the four matching edges $(a_i,b_i)$ removed. It is bipartite, so $\chi(G)=2$. Yet the interleaved order $a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4$ makes first-fit introduce a new color for every pair.

The topology is identical in both panels; only the processing order changes. On the left, each pair $(a_i,b_i)$ can reuse a color, but later pairs see all earlier colors. On the right, one side is colored first and the other side reuses a single second color.

local choices can create global wastesame graph, 4 colors or 2a valid coloring need not be minimum

Welsh-Powell: Degree-Descending Order

Welsh–Powell replaces an arbitrary order with a static proxy for difficulty: sort vertices by descending degree, then apply first-fit. High-degree vertices participate in many constraints, so resolving them early often prevents a lightly constrained choice from consuming a useful color first.

The proxy has a blind spot: degree counts neighbors, not the different colors those neighbors already use. It also cannot distinguish vertices in a regular graph. Every crown-graph vertex above has degree three, so a stable degree sort preserves the bad interleaved order.

DSatur: Saturation Degree Order

DSATUR measures urgency directly. For an uncolored vertex $v$, define

$$\operatorname{sat}(v)=\left|\{c(u):u\in N(v),\;u\text{ is colored}\}\right|.$$

This counts distinct neighbor colors, not colored neighbors. Five red neighbors contribute saturation one; one red, one navy, and one teal neighbor contribute saturation three.

Select maximum saturation

Choose the uncolored vertex facing the largest number of blocked colors.

Break ties by remaining degree

Prefer the tied vertex with more neighbors still uncolored; use the vertex index only to make the implementation deterministic.

Assign first-fit and update

Use the smallest available color, then add it to the saturation sets of uncolored neighbors.

Degree was identical for every original vertex, but saturation is already separating urgent vertices after two assignments. DSATUR follows the evolving boundary between colored and uncolored regions.

Worked Example

Use the crown graph from the SVG and deterministic ties by label. Arbitrary greedy and Welsh–Powell retain the interleaved order because every degree equals three. DSATUR instead creates the true bipartition.

Method	Selection or order	Color sequence	Total
Greedy	$a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4$	$0,0,1,1,2,2,3,3$	4
Welsh–Powell	same stable order; every degree is 3	$0,0,1,1,2,2,3,3$	4
DSATUR	$a_1,b_2,a_3,b_1,a_2,a_4,b_3,b_4$	$0,1,0,1,0,0,1,1$	2

This is not a proof that DSATUR always dominates degree ordering. It shows the information advantage of a dynamic priority: saturation observes how earlier colors interact, while degree alone never changes.

Choosing a Heuristic

Use arbitrary greedy when…

vertices arrive online, latency is critical, or an externally meaningful order already exists.

Use Welsh–Powell when…

you want a deterministic, inexpensive baseline with one preprocessing sort and no dynamic priority maintenance.

Use DSATUR when…

solution quality matters enough to spend quadratic time on a simple implementation, especially before exact search.

Use an exact method when…

you must prove optimality or feasibility with a fixed color budget. Feed it the heuristic coloring as an initial upper bound.

Complexity Analysis

Let $n=|V|$, $m=|E|$, and $\Delta$ be maximum degree. These bounds assume adjacency lists and a timestamp or set-based method for marking neighbor colors.

Heuristic	Ordering cost	Total time	General guarantee
Greedy	none when order is given	$O(n+m)$	valid coloring using at most $\Delta+1$ colors
Welsh–Powell	$O(n\log n)$ sort	$O(n\log n+m)$	same $\Delta+1$ bound; no general optimality guarantee
DSATUR, simple scan	$O(n)$ selection repeated $n$ times	$O(n^2+m)$ average with hash sets	same $\Delta+1$ bound; exact on some graph classes

A priority queue can reduce selection overhead in engineered DSATUR implementations, but saturation keys change dynamically and must be updated carefully. For teaching and moderate graphs, the $O(n^2+m)$ scan is compact, deterministic, and hard to get wrong.

Implementation

The implementations use the same conventions: a simple undirected adjacency list, deterministic label-based ties, first-fit color numbers beginning at zero, and the original Brélaz-style tie-break based on degree in the remaining uncolored graph.

def validate_undirected_graph(adj):
    """Return sorted, duplicate-free neighbors for a simple graph."""
    n = len(adj)
    neighbors = []
    for row in adj:
        clean = set()
        for v in row:
            if not isinstance(v, int) or not 0 <= v < n:
                raise ValueError("neighbor index out of range")
            clean.add(v)
        neighbors.append(clean)

    for u, row in enumerate(neighbors):
        if u in row:
            raise ValueError("self-loops make proper coloring impossible")
        for v in row:
            if u not in neighbors[v]:
                raise ValueError("adjacency list must be symmetric")
    return [sorted(row) for row in neighbors]


def _first_fit(neighbors, order):
    color = [-1] * len(neighbors)
    for u in order:
        blocked = {color[v] for v in neighbors[u] if color[v] != -1}
        c = 0
        while c in blocked:
            c += 1
        color[u] = c
    return color


def greedy_coloring(adj, order=None):
    """Color in the supplied permutation, or natural vertex order."""
    neighbors = validate_undirected_graph(adj)
    n = len(neighbors)
    if order is None:
        order = list(range(n))
    else:
        order = list(order)
        if len(order) != n or set(order) != set(range(n)):
            raise ValueError("order must be a permutation of all vertices")
    return _first_fit(neighbors, order)


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


def dsatur_coloring(adj):
    """DSATUR with remaining-degree and vertex-index tie-breaks."""
    neighbors = validate_undirected_graph(adj)
    n = len(neighbors)
    color = [-1] * n
    saturation = [set() for _ in range(n)]
    remaining_degree = [len(row) for row in neighbors]

    for _ in range(n):
        uncolored = (v for v in range(n) if color[v] == -1)
        best = max(uncolored,
                   key=lambda v: (len(saturation[v]),
                                  remaining_degree[v], -v))

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

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

    return color

# Crown graph: indices alternate a1,b1,a2,b2,...
left, right = [0, 2, 4, 6], [1, 3, 5, 7]
crown = [[] for _ in range(8)]
for i, u in enumerate(left):
    for j, v in enumerate(right):
        if i != j:
            crown[u].append(v)
            crown[v].append(u)

print("Greedy:", greedy_coloring(crown))
print("Welsh-Powell:", welsh_powell_coloring(crown))
print("DSATUR:", dsatur_coloring(crown))

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

using namespace std;

vector<int> greedyColoring(int n, const vector<vector<int>>& adj,
                           const 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, const 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) {
        if (adj[a].size() != adj[b].size())
            return adj[a].size() > adj[b].size();
        return a < b;
    });
    return greedyColoring(n, adj, order);
}

vector<int> dsaturColoring(int n, const vector<vector<int>>& adj) {
    vector<int> color(n, -1);
    vector<set<int>> saturation(n);
    vector<int> remainingDegree(n);
    for (int v = 0; v < n; v++) remainingDegree[v] = adj[v].size();
    int coloredCount = 0;

    while (coloredCount < n) {
        int best = -1;
        for (int v = 0; v < n; v++) {
            if (color[v] == -1) {
                if (best == -1 || saturation[v].size() > saturation[best].size() ||
                    (saturation[v].size() == saturation[best].size() &&
                     remainingDegree[v] > remainingDegree[best]) ||
                    (saturation[v].size() == saturation[best].size() &&
                     remainingDegree[v] == remainingDegree[best] && v < best)) {
                    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);
                remainingDegree[nb]--;
            }
        }
    }
    return color;
}

int main() {
    int n = 8;
    vector<vector<int>> adj(n);
    vector<int> left = {0, 2, 4, 6}, right = {1, 3, 5, 7};
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (i == j) continue;
            int u = left[i], v = right[j];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    vector<int> natural = {0,1,2,3,4,5,6,7};
    auto greedy = greedyColoring(n, adj, natural);
    auto wp = welshPowellColoring(n, adj);
    auto ds = dsaturColoring(n, adj);
    cout << "Greedy: ";
    for (int c : greedy) { cout << c << " "; }
    cout << "\nWelsh-Powell: ";
    for (int c : wp) { cout << c << " "; }
    cout << "\nDSATUR: ";
    for (int c : ds) { cout << c << " "; }
    cout << "\n";
    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[] remainingDegree = new int[n];
        for (int i = 0; i < n; i++) remainingDegree[i] = adj.get(i).size();
        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() &&
                         remainingDegree[v] > remainingDegree[best])) {
                        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);
                    remainingDegree[nb]--;
                }
            }
        }
        return color;
    }

    public static void main(String[] args) {
        int n = 8;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] left = {0,2,4,6}, right = {1,3,5,7};
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (i == j) continue;
                int u = left[i], v = right[j];
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }

        List<Integer> natural = Arrays.asList(0,1,2,3,4,5,6,7);
        System.out.println("Greedy: " + Arrays.toString(greedyColoring(n, adj, natural)));
        System.out.println("Welsh-Powell: " + Arrays.toString(welshPowellColoring(n, adj)));
        System.out.println("DSATUR: " + Arrays.toString(dsaturColoring(n, adj)));
    }
}

Real-World Applications

Coloring is a useful abstraction whenever pairwise conflicts forbid two objects from sharing a resource. The heuristic minimizes colors only indirectly, so the graph and the meaning of a color must match the real constraints.

Exam timetabling

Courses are vertices, a shared student creates an edge, and colors represent time slots. Room capacity and preferred times require additional constraints beyond plain coloring.

Register allocation

Simultaneously live program values interfere. Colors represent physical registers; when too few registers exist, a compiler may spill selected values to memory and rebuild the graph.

Frequency assignment

Nearby transmitters that would interfere become adjacent. Colors model channels, while real deployments may also need weighted separation and geographic constraints.

Exact-solver warm starts

A fast heuristic gives an initial upper bound. Branch-and-bound, SAT, or ILP solvers can prune any search state that cannot improve it.

Validate Before You Trust the Count

The color count is meaningful only after checking feasibility. Scan every edge once and confirm its endpoints differ; then compute $1+\max_v c(v)$ for a nonempty graph.

Exercises

1. Generalize the crown example

For $K_{r,r}$ minus a perfect matching, prove that the interleaved order $a_1,b_1,\ldots,a_r,b_r$ makes first-fit use $r$ colors although the graph is bipartite.

2. Prove the universal bound

Show directly that every sequential first-fit ordering uses at most $\Delta+1$ colors. Construct a graph where all $\Delta+1$ are necessary.

3. Separate saturation from colored degree

Draw two uncolored vertices with the same number of colored neighbors but different saturation degrees. Which one does DSATUR prioritize, and why?

4. Benchmark tie-breaking

Compare static degree and remaining degree as the DSATUR tie-break on random graphs. Report valid color counts, runtimes, and enough seeds to make the experiment reproducible.

5. Add an optimality proof

Use the DSATUR coloring as an upper bound in an exact $k$-colorability search. Combine it with a clique lower bound and stop when the bounds meet.

Limitations

Feasible Does Not Mean Optimal

These are constructive heuristics, not general approximation algorithms with a promised ratio. They quickly produce valid colorings, but the gap between the returned count and $\chi(G)$ can be large on adversarial graphs.

Ties are algorithmic choices: equal priorities are common. State the tie-break and keep it deterministic when reproducibility matters.
Labels are arbitrary: color 0 is not better than color 1. Renaming colors preserves the same partition.
Simple-graph assumptions matter: duplicate adjacency entries are harmless after normalization, but a self-loop makes proper coloring impossible.
Dynamic graphs need maintenance: adding or removing an edge can invalidate a coloring; recomputation or an incremental recoloring strategy may be required.
Extra constraints change the problem: capacities, preassigned colors, unavailable slots, and weighted conflicts require list coloring or a richer constraint model.

Cookie Consent

Graph Coloring Heuristics

Contents

A Short History of Coloring Heuristics

The Shared Greedy Core

Always feasible

An upper bound, not a proof of optimality

Greedy Coloring: Arbitrary Order

Read the next vertex

Mark forbidden colors

Choose first-fit

Why the $\Delta+1$ Bound Is Immediate

Why Order Matters: One Graph, Two Outcomes

Welsh-Powell: Degree-Descending Order

DSatur: Saturation Degree Order

Select maximum saturation

Break ties by remaining degree

Assign first-fit and update

Worked Example

Choosing a Heuristic

Use arbitrary greedy when…

Use Welsh–Powell when…

Use DSATUR when…

Use an exact method when…

Complexity Analysis

Implementation

Real-World Applications

Exam timetabling

Register allocation

Frequency assignment

Exact-solver warm starts

Validate Before You Trust the Count

Exercises

1. Generalize the crown example

2. Prove the universal bound

3. Separate saturation from colored degree

4. Benchmark tie-breaking

5. Add an optimality proof

Limitations

Feasible Does Not Mean Optimal

Cookie Consent

Graph Coloring Heuristics

Contents

A Short History of Coloring Heuristics

The Shared Greedy Core

Always feasible

An upper bound, not a proof of optimality

Greedy Coloring: Arbitrary Order

Read the next vertex

Mark forbidden colors

Choose first-fit

Why the $\Delta+1$ Bound Is Immediate

Why Order Matters: One Graph, Two Outcomes

Welsh-Powell: Degree-Descending Order

DSatur: Saturation Degree Order

Select maximum saturation

Break ties by remaining degree

Assign first-fit and update

Worked Example

Choosing a Heuristic

Use arbitrary greedy when…

Use Welsh–Powell when…

Use DSATUR when…

Use an exact method when…

Complexity Analysis

Implementation

Real-World Applications

Exam timetabling

Register allocation

Frequency assignment

Exact-solver warm starts

Validate Before You Trust the Count

Exercises

1. Generalize the crown example

2. Prove the universal bound

3. Separate saturation from colored degree

4. Benchmark tie-breaking

5. Add an optimality proof

Limitations

Feasible Does Not Mean Optimal

Related Deep Dives

Graph Theory Series

Bipartite Testing & k-Colorability Backtracking

Part 13: Graph Coloring