Graph Coloring

Math for CS · Axiom Academy

Chromatic number, greedy coloring, and the four color theorem — every vertex is adjacent to every other, so each needs a distinct color (if the tree has at least one edge) — trees are bipartite where is the clique number — the size of the largest complete subgraph. A clique of size k requires k colors. where is the maximum degree. This follows from the greedy algorithm (see below). The bound is tight for complete graphs and odd cycles, but often very loose. Brooks' theorem improves the naive bound by 1 for most graphs. It says the only graphs that truly need colors are complete graphs and odd cycles. The simplest coloring algorithm processes vertices one at a time, assigning each the smallest available color. Order the vertices (the choice of ordering matters). For each v_i in order, assign the smallest positive integer color not used by any already-colored neighbor of v_i . This means any map can be colored with 4 colors such that no two adjacent regions share a color. Conjectured in 1852, it was proved in 1976 by Appel and Haken — the first major theorem requiring computer verification. Applications of Graph Coloring In compiler optimization, variables that are "live" at the same time conflict. Build an interference graph (variables are vertices, edges connect simultaneously live variables). Coloring this graph assigns CPU registers — the chromatic number equals the minimum registers needed.

This is the written version of the interactive lesson above. See the full Math for CS course.