Chapter XII Chromatic Number

DSATUR in Java

DSATUR (Degree of Saturation, Brélaz 1979) — a greedy heuristic that's optimal on small graphs and very good on large ones.

Standard adjacency-list graph. Java's collections give us BitSet for color tracking; HashMap for the adjacency. The verbosity is the cost; the JIT pays you back.

import java.util.*;
public class Dsatur {
    int n;
    List<Set<Integer>> adj;
    public Dsatur(int n) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new HashSet<>());
    }
    public void edge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); }
}

Saturation degree of a vertex = number of distinct colors among its neighbors. DSATUR picks the next vertex to color as the one with maximum saturation, breaking ties by raw degree.

int saturation(int v, int[] color) {
    BitSet seen = new BitSet();
    for (int u : adj.get(v)) if (color[u] >= 0) seen.set(color[u]);
    return seen.cardinality();
}

int pickNext(int[] color) {
    int best = -1, bestSat = -1, bestDeg = -1;
    for (int v = 0; v < n; v++) {
        if (color[v] >= 0) continue;
        int sat = saturation(v, color), deg = adj.get(v).size();
        if (sat > bestSat || (sat == bestSat && deg > bestDeg)) {
            best = v; bestSat = sat; bestDeg = deg;
        }
    }
    return best;
}

Color each picked vertex with the smallest color not used by any neighbor. The maximum color index used is the answer (an upper bound on χ; on many graphs it's tight).

int[] color() {
    int[] c = new int[n];
    Arrays.fill(c, -1);
    for (int step = 0; step < n; step++) {
        int v = pickNext(c);
        BitSet used = new BitSet();
        for (int u : adj.get(v)) if (c[u] >= 0) used.set(c[u]);
        c[v] = used.nextClearBit(0);
    }
    return c;
}

Drive it on the Petersen graph (chromatic number 3). DSATUR returns three colors. For exact chromatic number on harder graphs you'd add branch-and-bound on top — that's roughly what the Held-Karp-style bounds give you.

public static void main(String[] args) {
    Dsatur g = new Dsatur(10);
    int[][] e = {{0,1},{1,2},{2,3},{3,4},{4,0},
                 {5,7},{7,9},{9,6},{6,8},{8,5},
                 {0,5},{1,6},{2,7},{3,8},{4,9}};
    for (int[] x : e) g.edge(x[0], x[1]);
    System.out.println(Arrays.toString(g.color())); // uses 3 colors
}

Grammar — Java

Java is verbose by design — explicit types, classes, and visibility modifiers — and the JIT pays you back with speed once it warms up. Graph algorithms read as plain procedural code wrapped in a class.

import java.util.*;: wildcard import of a package. java.util gives you ArrayList, HashMap, BitSet, Arrays, etc.
public class C { ... }: every Java file declares one class. public means visible everywhere; the file name must match.
List<T>: a generic interface. The angle-brackets carry the element type.
new HashMap<>(): allocate a HashMap. The empty `<>` lets the compiler infer the generic types from context.
BitSet: a built-in dynamic bitset. Faster than `Set<Integer>` for dense small-integer sets.
for (int x : arr): enhanced for loop. Iterates an array or anything implementing Iterable.
Arrays.fill(arr, -1): utility method: set every element of arr to -1. Look in Arrays/Collections/Math for utilities.
Math.max(a, b): standard math. Most numeric utilities live in java.lang.Math.
static T method(...): a static method — call without an instance, like Dsatur.color() rather than dsatur.color().

Adjacency list with a Set per vertex — duplicates prevented, membership tests cheap. ArrayList of HashSet is the standard idiom.

List<Set<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new HashSet<>());

void edge(int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);
}

Java — official tutorial trail →