Scheduling exams so that no student has two at once, assigning radio frequencies so that neighbors don't interfere, coloring a map: each is coloring the vertices of a graph. It uses cycles and the special graphs, especially bipartite ones.
Key idea
A proper coloring gives each vertex a color so that joined vertices get different colors. The chromatic number $\chi(G)$ is the fewest colors that work. $\chi(K_{n}) = n$; $\chi(C_{n}) = 2$ for even $n$ and $3$ for odd $n$; and a graph with at least one edge has $\chi(G) = 2$ exactly when it has no cycle of odd length (it is bipartite).
Why it works
Going around a cycle, two colors must alternate. Around an even cycle that works; around an odd cycle the last vertex ends up next to a vertex of its own color. So any odd cycle forces a third color. Conversely, if there is no odd cycle, color a starting vertex red, its neighbors blue, their neighbors red, and so on outward; a clash would mean two routes of different parity between the same vertices, which together contain an odd cycle. To show $\chi(G) = k$, you always need two things: a coloring with $k$ colors, and a reason $k - 1$ is not enough.
Worked examples
Worked example: A wheel
A wheel has a 5-cycle rim and a hub joined to all five rim vertices. Find its chromatic number.
- The rim is an odd cycle, so it needs $3$ colors.
- The hub is joined to every rim vertex, so it cannot reuse any rim color: a $4$th color.
- Four colors suffice (three on the rim, one on the hub), so $\chi = 4$.
Answer: $4$
Worked example: Scheduling exams
Exams A–E: A conflicts with B and C; B with C and D; D with E. How many time slots are needed?
- Vertices are exams, edges are conflicts, slots are colors.
- $A$, $B$, $C$ form a triangle, so at least $3$ slots.
- Three work: slot 1: $A, D$; slot 2: $B, E$; slot 3: $C$. Check every conflict: no edge joins two exams in one slot.
Answer: $3$
Worked example: Greedy coloring depends on order
The path $a - b - c - d$ is colored greedily in the order $a, d, b, c$: each vertex takes the lowest-numbered color not used by its colored neighbors. How many colors are used?
- $a$ gets $1$. $d$ gets $1$ (no colored neighbors yet).
- $b$ is next to $a$ (color $1$), so it gets $2$. $c$ is next to $b$ ($2$) and $d$ ($1$), so it gets $3$.
- Three colors, although the path is bipartite and $2$ colors suffice (order $a, b, c, d$ gives $1, 2, 1, 2$).
Answer: $3$
Common mistake
Trusting a greedy coloring to be optimal. Greedy coloring is fast and never uses more than one color beyond the largest degree, but the number it uses depends on the order of the vertices, as the path example shows. Check: a coloring only gives an upper bound; to know $\chi(G)$, also find a reason fewer colors fail, such as an odd cycle or a group of vertices all joined to each other.