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.
This notation separates two questions that are easy to mix up: can I produce a valid coloring with \(k\) colors? and is \(k\) the minimum possible? Greedy algorithms answer the first quickly; proving optimality requires a matching lower bound.
Coloring is really “separate every conflict”
Each edge means “these two vertices are not allowed to share a color.” A proper coloring therefore partitions the vertices into groups with no internal edges. Those groups are exactly independent sets. The chromatic number asks for the smallest number of such groups that can cover every vertex.
Memory hook: complete graphs force “everyone different,” bipartite graphs permit “two teams,” and an odd cycle is the smallest reason two-team coloring can fail.
Key Insight
Graph coloring is really a partitioning problem in disguise: each color class is an independent set (Part 4's vocabulary — no two vertices in it are adjacent). \(\chi(G)\) is exactly the minimum number of independent sets needed to partition \(V(G)\). In scheduling language, a color is a time slot; in register allocation, it is a register; in frequency assignment, it is a channel. The mathematics is the same conflict-partitioning problem every time.
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.
The same bipartite graph can make greedy use 3 colors or 2
Greedy coloring never “looks ahead.” It only avoids colors already used by colored neighbors. On the crown graph below, the deliberately awkward order \(a_1,b_1,a_2,b_2,a_3,b_3\) forces a third color even though the graph is bipartite and therefore has \(\chi(G)=2\).
Why heuristics exist
The coloring rule itself is easy; choosing a good order is the hard part. Welsh-Powell makes one static guess (“high degree first”), while DSatur repeatedly asks a dynamic question: which uncolored vertex is currently most constrained by distinct neighboring colors?
Saturation counts distinct neighboring colors, not colored neighbors
A vertex surrounded by three different colors is more urgent than one surrounded by three neighbors that all use the same color. DSatur prioritizes the vertex with the larger saturation degree because its remaining options are disappearing fastest.
Why practical coloring uses heuristics
Additional complexity context: finding the exact chromatic number is computationally hard in general; even deciding whether an arbitrary graph is 3-colorable is NP-complete. That is why real systems often combine greedy/DSatur-style heuristics, lower bounds, and backtracking rather than expecting one fast algorithm to always return \(\chi(G)\).
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.
Bounds are useful because computing the exact chromatic number can be difficult. A large clique gives an immediate lower bound: if the graph contains a complete subgraph on \(r\) vertices, those \(r\) vertices are pairwise adjacent and must all receive different colors. Writing \(\omega(G)\) for the clique number:
Lower bounds say “you need at least this many”; upper bounds say “this many will always suffice”
Brooks' theorem is best remembered as: the greedy-looking bound \(\Delta+1\) is almost always one color too pessimistic; complete graphs and odd cycles are exactly the connected exceptions.
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).
The Four Color Theorem is a vertex-coloring theorem in disguise
Turn each region into a vertex and connect two vertices exactly when their regions share a non-zero-length border. Then “neighboring countries need different colors” becomes ordinary proper vertex coloring. Regions that touch only at a single corner are not adjacent in the map-coloring model.
Four colors are an upper bound, not a claim that every map needs four. Trees need only two; many planar maps need three; some genuinely require four.
The Proof That Broke Mathematical Tradition
In 1976, Kenneth Appel and Wolfgang Haken finally proved the Four Color Theorem — but their proof reduced the infinite space of possible planar maps to 1,936 unavoidable configurations, then used a computer to mechanically check every one. It was the first major theorem in mathematical history whose proof could not be verified by a human reading it line by line, sparking genuine philosophical debate: is a proof no human can fully check still a proof? The result has since been independently reverified by different computer methods, but the debate it started about the nature of mathematical proof itself continues to this day.
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.
The lower bound is immediate: if some vertex has degree \(\Delta\), then all \(\Delta\) edges touching that vertex conflict pairwise and must receive different colors. Vizing's theorem says the entire graph needs at most one extra color beyond that unavoidable local requirement.
Class One uses exactly Δ colors; Class Two needs the one extra color Vizing allows
A useful bridge between the two problems
Edge coloring of \(G\) is exactly vertex coloring of its line graph \(L(G)\): make one vertex in \(L(G)\) for every edge of \(G\), and connect two line-graph vertices when the original edges share an endpoint.
Real-World Applications
Register Allocation in Compilers
A compiler must assign a program's variables to a small, fixed number of CPU registers, never assigning the same register to two variables that are simultaneously "live" (still needed later in the program). Build an interference graph — one vertex per variable, an edge between any two variables live at the same time — and register allocation becomes exactly graph coloring, with the number of physical registers as the color budget. When \(\chi(G)\) exceeds the register count, the compiler "spills" some variables to slower memory — a direct, practical consequence of the chromatic number being too high.
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
- Compute \(\chi(K_{3,3})\) using the bipartite characterization, and verify greedy coloring in vertex order A,B,C,D,E,F achieves it.
- 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.
- 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)\).
- 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.
Next in the Series
In Part 14: The Traveling Salesman Problem, we meet one of the most studied NP-hard problems in all of computer science, and the exact and approximate algorithms built to attack it anyway.