Chapter 33 — Key Takeaways
Graph Coloring, Planarity, and the Four Color Theorem — the re-grounding card. Reread this before an exam.
Core definitions
| Term | Definition |
|---|---|
| Proper coloring | $c\colon V \to \{1,\dots,k\}$ with $c(u)\neq c(v)$ for every edge $\{u,v\}$ |
| $k$-colorable | A proper coloring with $k$ colors exists |
| Chromatic number $\chi(G)$ | The smallest $k$ for which $G$ is $k$-colorable |
| Clique number $\omega(G)$ | Size of the largest set of pairwise-adjacent vertices |
| Color class / independent set | All vertices of one color; no two are adjacent |
| Planar graph | Drawable in the plane with no edge crossings |
| Plane graph | A planar graph together with a specific crossing-free drawing |
| Face | A region (incl. the outer/unbounded face) the drawing cuts the plane into |
| Subdivision | Replace edges with paths (insert degree-2 vertices) — preserves planarity |
The bounds you must know
$$\omega(G) \;\le\; \chi(G) \;\le\; \Delta(G) + 1$$
| Bound | Direction | Why | Tight when |
|---|---|---|---|
| $\chi \ge \omega$ | lower | A clique forces distinct colors | $K_n$ (=$n$); register pressure |
| $\chi \le \Delta+1$ | upper | Greedy never runs out of colors | $K_n$, odd cycles |
Pitfall: $\chi \ge \omega$ is a lower bound only — NOT equality. $C_5$ has $\omega=2$ but $\chi=3$.
Standard chromatic numbers (memorize)
| Graph | $\chi$ |
|---|---|
| Edgeless graph | $1$ |
| Bipartite graph (with $\ge 1$ edge) | $2$ |
| Tree (with $\ge 1$ edge) | $2$ |
| Cycle $C_n$, even $n$ | $2$ |
| Cycle $C_n$, odd $n$ | $3$ |
| Complete graph $K_n$ | $n$ |
| Complete bipartite $K_{m,n}$ | $2$ |
| Any planar graph | $\le 4$ (Four Color Theorem) |
2-colorability triad: $\chi(G)=2 \iff G$ bipartite $\iff G$ has no odd cycle. Test in linear time with BFS layer-parity (an edge inside one layer = odd cycle = not bipartite).
Planarity toolkit
Euler's formula (connected plane graph): $$V - E + F = 2$$
Edge bounds (simple, connected, planar, $V \ge 3$):
| Condition | Bound |
|---|---|
| General | $E \le 3V - 6$ |
| Triangle-free | $E \le 2V - 4$ |
Non-planarity certificates:
| Graph | $V$ | $E$ | Bound it breaks |
|---|---|---|---|
| $K_5$ | 5 | 10 | $10 > 3(5)-6 = 9$ |
| $K_{3,3}$ | 6 | 9 | $9 > 2(6)-4 = 8$ (triangle-free bound) |
Pitfall: $E \le 3V-6$ is necessary, not sufficient. Failing it ⇒ non-planar (certificate). Passing it ⇏ planar ($K_{3,3}$ passes the general bound; needs the triangle-free one).
Kuratowski's theorem: $G$ planar $\iff$ $G$ contains no subdivision of $K_5$ or $K_{3,3}$. (Wagner: same with "minor.") These two graphs are the only obstructions.
The Four Color Theorem — what it does and doesn't say
| Claim | True? |
|---|---|
| Every planar graph is 4-colorable | ✅ Yes (Appel–Haken 1976) |
| 4 colors are sometimes necessary | ✅ Yes ($K_4$ drawn as a map) |
| Every graph is 4-colorable | ❌ No — non-planar only ($\chi(K_5)=5$) |
| Deciding planar 3-colorability is easy | ❌ No — still NP-complete |
- History: conjectured 1852 (Guthrie) → Kempe's flawed proof (1879, accepted 11 yrs) → gap found + five-color theorem (Heawood 1890) → proved by computer (Appel–Haken 1976) → formally verified in Coq (Gonthier–Werner 2005).
- Why it matters (threshold concept): first major theorem no human can hand-check — forced the question "is a proof a person can't survey still a proof?" For programmers: the same trust question we face shipping any computation.
Greedy coloring
Rule: process vertices in some order; give each the smallest color no already-colored neighbor uses.
| Property | Status |
|---|---|
| Always proper | ✅ |
| Uses $\le \Delta(G)+1$ colors | ✅ (any order) |
| Optimal ($=\chi$) | ❌ Not in general |
| Result depends on vertex order | ⚠️ Heavily |
Worst case: the crown graph ($a_i b_j$ for $i\neq j$) is bipartite ($\chi=2$) but the interleaved order $a_1,b_1,a_2,b_2,\dots$ makes greedy use $n$ colors.
Better orders (heuristics, not optimal): - Welsh–Powell — decreasing degree (hard vertices first). - Smallest-last — repeatedly remove a min-degree vertex; color in reverse. (≤ 6 colors on planar graphs.)
Coloring is NP-hard — no poly-time rule can be always-optimal (Ch. 37).
Modeling recipe (the why-it-matters)
| Application | Vertices | Edges (conflict) | Colors | $\chi$ means |
|---|---|---|---|---|
| Exam scheduling | exams | share a student | time slots | min # of periods |
| Register allocation | program values | live at same time (interfere) | CPU registers | min registers (else spill) |
| Frequency assignment | towers | overlap range | frequencies | min spectrum |
| Map coloring | regions | share a border | colors | (≤ 4, planar) |
Color class = independent set = a group of mutual non-conflicters (social-graph: mutual strangers).
Toolkit additions (dmtoolkit/graphs.py)
| Function | Does | Cost |
|---|---|---|
greedy_coloring(g, order=None) |
proper coloring via greedy rule → {vertex: color} |
$O(V+E)$, not minimal |
chromatic_number(g) |
exact $\chi$ by brute force | exponential — small graphs only |
Use chromatic_number to measure how far greedy_coloring is from optimal on small instances. Feeds the capstone social-network analyzer (Ch. 39, Track B).
One-line reminders
- Coloring = separate conflicting things with the fewest resources.
- $\omega \le \chi \le \Delta+1$, always.
- Bipartite ⇔ 2-colorable ⇔ no odd cycle.
- Euler: $V - E + F = 2$ ⇒ $E \le 3V-6$ ⇒ $K_5, K_{3,3}$ non-planar.
- Planar ⇒ 4-colorable (but the proof needed a computer).
- Greedy is fast and proper but order-dependent and not optimal.