Assigning Radio Frequencies with Graph Coloring

Nearby cell towers interfere if they broadcast on the same frequency. Join every pair of close towers with an edge: assigning frequencies so that no edge joins two equal ones is graph coloring, and the fewest frequencies that work is the graph's chromatic number.

How it works

Graph coloring and the chromatic number

In one sentence

A proper coloring assigns colors $c: V \to \{1, \dots, k\}$ with $c(u) \ne c(v)$ for every edge, and $\chi(G)$ is the least such $k$ . Deciding whether $\chi(G) \le 3$ is NP-complete in general, but greedy coloring always uses at most $\Delta(G) + 1$ colors, where $\Delta$ is the maximum degree.

General formula

{\htmlData{sym=0}{c(u)}} \ne c(v) \text{ for every edge } \{u, v\}, \qquad {\htmlData{sym=1}{\chi(G)}} = \text{fewest colors possible}

Each edge is a 'can't share' rule. Coloring satisfies every rule at once with as few colors as possible.

What the symbols mean

$c(u)$
Frequency of tower u
The color (channel) assigned to tower u.
$\chi(G)$
Chromatic number
The fewest frequencies that avoid all interference.

Build the conflict graph: one vertex per tower, and an edge between any two towers close enough to interfere.
A frequency plan is a coloring: adjacent vertices get different colors. The chromatic number $\chi(G)$ is the fewest frequencies that can work.
Any triangle of mutually interfering towers forces at least 3 frequencies. Greedy assignment, giving each tower the lowest frequency its neighbors aren't using, never needs more than one more than the largest number of neighbors.
A bigger interference range adds edges and can push the chromatic number up, so planners trade coverage against the number of frequencies they must license.

Learn the math

Graphs, Degrees and the Handshake LemmaDiscrete · Lesson 37, Graph Theory Planar Graphs and ColoringDiscrete · Lesson 41, Graph Theory