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.
Idea clave
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).
Por qué funciona
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
Ejemplo resuelto: 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$.
Respuesta: $4$
Ejemplo resuelto: 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.
Respuesta: $3$
Ejemplo resuelto: 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$).
Respuesta: $3$
Error común
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.