DCI'00

Fred S. Roberts

DIMACS/Rutgers University

From Garbage to Rainbows: The Many Applications of Graph Coloring


The simple concept of coloring a graph has a long history and has been a fundamental idea in graph theory. This talk will survey its many applications, such as channel assignments in telecommunications, task scheduling, traffic phasing, fleet assignment, and mobile radio frequency assignment. We will also describe generalizations of the standard notion of graph coloring that arise from applications.