and Theoretical Computer Science

June 19-30, 2000

Algorithms for Graph Coloring.

A coloring of a graph G is an assignment of colors to vertices so that
no two adjacent vertices have the same color. The Chromatic Number of
a graph is the minimum number of colors that are needed to color it --
for example, the Four-Color Theorem implies that all planar graphs
have Chromatic Number at most 4.

These lectures will consider
the algorithmic problem of finding colorings of graphs that use as few
colors as possible. We will survey applications of the Graph Coloring
problem, such as assigning classrooms (colors) to college courses
(vertices) under the constraint that courses meeting at the same time
cannot be in the same room (marked by edges).

Since the
general Graph Coloring problem is known to be NP-Hard, there is not
likely to be an efficient algorithm that can find guaranteed
minimum-color colorings for all graphs. We will discuss the theory of
NP-Completeness and its application to Graph Coloring, and will
examine several recently-proposed graph-coloring algorithms.
Depending on background, participants will be invited to carry out
small experimental research projects to evaluate these algorithms.

Prerequisites for this topic include: A familiarity with proofs
and elementary graph theory. An ability to write simple computer
programs is desirable, but not necessary to come away with something
useful.