tion of vertices (the task squares in our diagram) with arrows connecting
some of them to indicate which tasks must be performed before other
tasks. Instead of drawing arrows, which indicate a direction, we might
just draw lines connecting some of the vertices. This is very much like
an intracity road map, with cities represented by hollow circles at the
vertices and lines (which are called edges) connecting the cities indicat-
ing major highways (or not so major ones, if you’re out in a rural area). A
graph is a collection of vertices and edges; two vertices may or may not
be connected by an edge, but two cities cannot be connected by more
than one edge.
Suppose we decided to fill in each of the hollow circles with a color, sub-
ject only to the following rule: if two vertices (the hollow circles) are con-
nected by an edge, they must be colored differently. Obviously, one way to
do this is simply to color each city a different color. The graph coloring
problem is to determine the minimum number of colors needed to color
vertices connected by an edge with different colors.
Mathematicians always like to point out how the most seemingly ab-
stract problem can have unexpected practical applications. The graph
coloring problem has lots of these. One such rather surprising applica-
tion is the assignment of frequencies to users of the electromagnetic
spectrum, such as mobile radios or cell phones. Two users who are close
to each other cannot share the same frequency, whereas distant users
can. The frequencies correspond to the colors.
The Big Question
The big question in this area, one of the Clay Mathematics Institute’s
million-dollar babies, is whether the tough problems that have been de-
scribed in this section can be done in polynomial time. Interestingly
enough, while an affirmative answer to this question would mean that
speedy ways of scheduling or planning routes for the traveling salesman
exist (at least in theory; we’d still have to find them), a negative answer
would have an upside as well! There is one very important problem for
which a negative answer would be highly satisfactory: the factorization
problem.
The problem of whether an integer can be factored is, like scheduling
and graph coloring, known to be one of Cook’s tough cookies. If no poly-
nomial time algorithm exists for doing so, those of us who have bank ac-
counts can breathe a little easier, because as described in the introduction,
the difficulty of factoring numbers that are the product of two primes is
key to the security of many password-protected systems.Murphy’s Law 165