Part 13: Graph Coloring

Coloring Fundamentals

A proper vertex coloring assigns a color to every vertex so that no edge connects two vertices of the same color. The chromatic number \(\chi(G)\) is the minimum number of colors needed. A few quick facts follow directly from earlier parts: \(\chi(K_n) = n\) (every vertex is adjacent to every other), \(\chi(C_n) = 2\) if \(n\) is even and \(3\) if \(n\) is odd (odd cycles are exactly the obstruction to bipartiteness from Part 5), and — precisely because of that bipartiteness link — \(\chi(G) \leq 2\) if and only if \(G\) is bipartite.

Greedy Coloring & Heuristics

The simplest algorithm: process vertices in any order, assigning each the lowest-numbered color not already used by an already-colored neighbor. This always produces a valid coloring, but not necessarily an optimal one — vertex order matters enormously. Two classic heuristics improve on arbitrary ordering:

• Welsh-Powell: sort vertices by decreasing degree first, then greedily color — high-degree "hub" vertices get first pick of colors, when the most options are still available.
• DSatur (degree of saturation): at each step, color the uncolored vertex with the most distinct colors already among its neighbors (breaking ties by degree) — a more adaptive strategy that reacts to the coloring as it develops rather than committing to a fixed order upfront.

def greedy_coloring(vertices, adj, order=None):
    """order: list controlling processing order (defaults to input order)."""
    order = order or vertices
    color = {}
    for v in order:
        used = {color[u] for u in adj[v] if u in color}
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

adj = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
print(greedy_coloring(["A", "B", "C", "D"], adj))  # {'A': 0, 'B': 1, 'C': 2, 'D': 0}

Bounding the Chromatic Number

A trivial upper bound: \(\chi(G) \leq \Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree (greedy coloring never needs more colors than "one more than the most crowded neighborhood"). Brooks' theorem (R. Leonard Brooks, 1941) sharpens this dramatically: for any connected graph that is neither a complete graph nor an odd cycle, \(\chi(G) \leq \Delta(G)\) — one fewer color than the naive bound, in nearly every case.

The Four Color Theorem

The most famous coloring question of all: can every planar graph (Part 17's subject — think of countries on a flat map, sharing borders) always be colored with just four colors? The conjecture was first posed in 1852 by Francis Guthrie, a student trying to color a map of England's counties, and passed along by his brother to the mathematician Augustus De Morgan. It resisted proof for over a century, attracting — and defeating — many serious attempted proofs (including a famous flawed 1879 "proof" by Alfred Kempe that stood unchallenged for 11 years before an error was found).

Edge Coloring & Vizing's Theorem

Edge coloring assigns colors to edges so that no two edges sharing a vertex have the same color; the minimum number needed is the chromatic index \(\chi'(G)\). Vizing's theorem (Vadim Vizing, 1964) proves \(\chi'(G)\) is always either \(\Delta(G)\) (a "Class One" graph) or \(\Delta(G) + 1\) (a "Class Two" graph) — never anything else, an extraordinarily tight two-value classification for a problem that, for vertex coloring, has no such simple bound at all.

Real-World Applications

Beyond compilers: exam and meeting scheduling (conflicting exams/meetings as edges, time slots as colors), wireless frequency assignment (interfering transmitters as edges, frequencies as colors), and, of course, literal map coloring — the problem's original 1852 motivation.

Exercises

1. Compute \(\chi(K_{3,3})\) using the bipartite characterization, and verify greedy coloring in vertex order A,B,C,D,E,F achieves it.
2. Construct a graph where greedy coloring in a poor vertex order uses far more colors than \(\chi(G)\) — the classic example is a "crown graph" or a carefully ordered bipartite graph.
3. Verify Brooks' theorem's two exceptions by computing \(\chi(K_4)\) and \(\chi(C_5)\), and confirming both equal \(\Delta(G) + 1\), not \(\Delta(G)\).
4. Challenge: Implement DSatur and compare the number of colors it uses against plain greedy coloring (arbitrary order) on 20 random graphs — DSatur should win or tie in nearly every case.

Conclusion & Next Steps

Graph coloring connects independent sets, planarity, and — through the Four Color Theorem — the very nature of mathematical proof itself. Vizing's theorem shows edge coloring is far more tightly bounded than its vertex-coloring cousin. Next, we turn to a problem that sounds almost like Hamiltonian cycles from Part 12, but asks for something much stronger: not just a tour, but the cheapest possible one.