DIMACS
The Center for Discrete Mathematics
and Theoretical Computer Science


Reconnect Conference 2000
Reconnecting Teaching Faculty to the Mathematical Sciences Enterprise

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.

Back to Main Page