Graph Coloring & Planarity
Graph Coloring & Planarity
A proper $k$-coloring assigns colors $\{1,\ldots,k\}$ to vertices such that adjacent vertices get different colors. The chromatic number $\chi(G)$ is the minimum $k$. Graph coloring models scheduling, register allocation, and map coloring. The Four Color Theorem (proved by computer in 1976) states $\chi(G)\leq 4$ for every planar graph. A graph is planar iff it contains no $K_5$ or $K_{3,3}$ minor (Kuratowski's theorem).
Chromatic Number & Coloring Bounds
$\chi(G)\geq\omega(G)$ (clique number: largest complete subgraph). For bipartite graphs: $\chi=2$ (iff no odd cycles). Upper bounds: $\chi(G)\leq\Delta(G)+1$ (greedy coloring, $\Delta=$ max degree; Brooks' theorem: equality iff $G=K_n$ or odd cycle). The chromatic polynomial $P(G,k)$ counts proper $k$-colorings; $P(K_n,k)=k(k-1)\cdots(k-n+1)$; $P(C_n,k)=(k-1)^n+(-1)^n(k-1)$.
Kuratowski's Theorem & Euler's Formula
A graph is planar iff it has no subdivision of $K_5$ or $K_{3,3}$ as a subgraph (Kuratowski, 1930). For a connected planar graph: $v-e+f=2$ (Euler's formula, $f=$ faces including outer). Consequence: $e\leq 3v-6$ (since each face $\geq 3$ edges, $2e\geq 3f$, combined with Euler). $K_5$: $e=10>3(5)-6=9$; $K_{3,3}$: $e=9>2(6)-4=8$ (bipartite, each face $\geq 4$ edges). Both non-planar.
Example 1
Determine $\chi(C_7)$ and $\chi(K_{3,3})$.
Solution: $C_7$: odd cycle (7 vertices). Need $\chi\geq 2$ (not bipartite, no 2-coloring). Need $\chi\leq 3$: color alternately $1,2,1,2,1,2,1$; last vertex adjacent to first (color 1) and previous (color 2), needs color 3. So $\chi(C_7)=3$. $K_{3,3}$: bipartite (parts $\{1,3,5\}$ and $\{2,4,6\}$); 2-color the parts: $\chi(K_{3,3})=2$.
Example 2
Prove $K_5$ is non-planar using Euler's formula.
Solution: Suppose $K_5$ is planar. $v=5$, $e=10$. Euler: $v-e+f=2$, so $f=2-5+10=7$. Each face is bounded by $\geq 3$ edges; each edge borders 2 faces: $2e\geq 3f$, i.e., $20\geq 21$. Contradiction. So $K_5$ is non-planar.
Practice
- Prove the Five Color Theorem: every planar graph is 5-colorable.
- Compute $\chi(G)$ for the Petersen graph and show it equals 3.
- Use the deletion-contraction formula to compute $P(K_3,k)=(k)(k-1)(k-2)$.
- Show that $\chi(G)\cdot\chi(\bar{G})\geq n$ where $\bar{G}$ is the complement of $G$.
Show Answer Key
1. By Euler's formula ($v-e+f=2$) and $e\le3v-6$ for planar graphs: $\delta(G)\le5$ (some vertex has degree $\le5$). Induct: remove $v$ with $\deg\le5$, 5-color $G-v$, and reinsert $v$. At most 5 neighbors use at most 5 colors. If only 4 colors used among neighbors, assign the 5th. If all 5 used, a Kempe-chain argument frees a color.
2. The Petersen graph has girth 5 (no 3- or 4-cycles), so $\chi\ge3$. A valid 3-coloring exists (verified by construction or noting it's vertex-transitive with independence number 4). So $\chi=3$.
3. $P(K_3,k)$: vertex 1 gets $k$ colors, vertex 2 gets $k-1$ (not 1's color), vertex 3 gets $k-2$ (not 1's or 2's). $P(K_3,k)=k(k-1)(k-2)$.
4. In any proper coloring of $G$, each color class is independent. $\alpha(G)\ge n/\chi(G)$, so $\chi(G)\ge n/\alpha(G)$. Similarly $\chi(\bar{G})\ge n/\alpha(\bar{G})$. Since $\alpha(G)\cdot\alpha(\bar{G})\le n$ (a clique in $\bar{G}$ is independent in $G$), multiplying gives $\chi(G)\chi(\bar{G})\ge n$.