Lesson 9 · Problem-solving methods

Graph Coloring

Graph coloring assigns colors so adjacent vertices differ; greedy coloring is fast but exact minimum coloring is computationally hard in general.

What a coloring represents

A proper vertex coloring maps each vertex to a color such that endpoints of every edge differ. The smallest possible number is the chromatic number. Colors model mutually conflicting time slots, registers, frequencies, or resources; their names have no meaning beyond equality and difference.

A self-loop makes proper coloring impossible because a vertex would need to differ from itself. Parallel edges add no new constraint. Bipartite graphs need at most two colors and can be recognized by BFS or DFS parity, while general k-colorability is NP-complete for k≥3.

Adjacent endpoints must differ
Self-loops are immediate failure
Two-coloring is bipartite testing

Greedy coloring and ordering

Process vertices in an order and assign the smallest color unused by already colored neighbors. This always returns a proper coloring and uses at most Δ+1 colors, but it need not find the chromatic number. The same graph can use dramatically different counts under different orders.

Largest-degree-first and DSATUR are ordering heuristics, not optimality proofs. DSATUR chooses the uncolored vertex seeing the most distinct neighbor colors, then breaks ties by degree. It often performs well because it resolves the most constrained decision early.

Smallest available color preserves validity
Ordering controls solution quality
Heuristics improve practice, not worst-case optimality

Key reference

Terms, operations, and practical uses

Coloring terms

Proper coloringProper coloring is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Chromatic numberChromatic number is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Color classColor class is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Algorithms

Greedy coloringGreedy coloring is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
DSATURDSATUR is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
k-coloringk-coloring is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Bounds and cases

Clique lower boundClique lower bound is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Greedy upper boundGreedy upper bound is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Self-loopSelf-loop is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Greedy coloring assigns the smallest safe color

g=[[1,2,3],[0,2],[0,1,3],[0,2]];color=[-1]*4
for u in range(4):
    used={color[v] for v in g[u] if color[v]>=0}
    c=0
    while c in used:c+=1
    color[u]=c
print("Colors used:",max(color)+1)

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<vector<int>> g={{1,2,3},{0,2},{0,1,3},{0,2}};
    vector<int> color(4,-1);
    for(int u=0;u<4;u++) {
        set<int> used;
        for(int v:g[u]) if(color[v]>=0) used.insert(color[v]);
        int c=0;
        while(used.count(c)) c++;
        color[u]=c;
    }
    cout << "Colors used: " << *max_element(color.begin(),color.end())+1 << '\n';
}

import java.util.*;
class Main {
    public static void main(String[] args) {
        int[][] g={{1,2,3},{0,2},{0,1,3},{0,2}};
        int[] color={-1,-1,-1,-1};
        for(int u=0;u<4;u++) {
            Set<Integer> used=new HashSet<>();
            for(int v:g[u]) if(color[v]>=0) used.add(color[v]);
            int c=0;
            while(used.contains(c)) c++;
            color[u]=c;
        }
        System.out.println("Colors used: "+(Arrays.stream(color).max().orElse(-1)+1));
    }
}

Watch it run

Step through it

Running on cycle A-B-C-D-A plus A-C

Output

Exact k-coloring with backtracking

For a requested k, choose an uncolored vertex, try each color absent from its colored neighbors, recurse, and undo on failure. Selecting a constrained vertex first and trying less disruptive colors first can prune the search tree. A complete failed search proves no k-coloring exists.

The worst case is exponential, roughly O(k^V) before pruning. Symmetry can be reduced by fixing the first vertex to color zero and introducing colors in a canonical order; permuting color names otherwise repeats equivalent branches.

Choose, test, recurse, undo
Constraint ordering increases pruning
Fix color symmetry when possible

Correctness and lower bounds

Every returned assignment is checked edge by edge, giving an immediate validity proof. Optimality requires showing that no coloring with fewer colors exists, typically by repeated k-colorability tests or branch-and-bound. A clique of size q provides a lower bound q because all clique vertices are pairwise adjacent.

An upper bound comes from any valid greedy coloring. Branch-and-bound searches between these bounds and abandons a partial assignment once it cannot improve the incumbent. Confusing a greedy upper bound with the chromatic number is the most common conceptual error.

Cliques provide lower bounds
Greedy provides an upper bound
Validity is easier than minimality

Edge cases and applications

Disconnected components may be colored independently while reusing the same palette; the graph’s chromatic number is the maximum across components, not their sum. Empty graphs need zero colors by one convention, while a nonempty edgeless graph needs one.

Test cliques, odd and even cycles, disconnected components, isolated vertices, self-loops, and an ordering that makes greedy use extra colors. Register allocation adds spilling and interference-graph construction, so practical compiler coloring is more than the bare mathematical problem.

Reuse colors across components
Odd cycles need at least three colors
State empty-graph conventions

Choosing a solver by the requested guarantee

If the task asks for any valid schedule, greedy coloring may be sufficient and scales linearly in adjacency size plus color checks. If it asks whether k colors suffice, use constraint propagation and complete backtracking for small graphs. If it asks for the minimum, maintain lower and upper bounds and prove the gap closed.

Bitsets accelerate neighbor-color tests and exact solvers on modest V. A coloring certificate is cheap to verify, whereas proving optimality can dominate runtime. Communicate which guarantee was computed; calling a heuristic result 'the chromatic number' is a correctness defect even when it looks compact.

Any, k-feasible, and minimum are different tasks
Certificates verify assignments cheaply
Optimality needs a lower-bound proof