Clique and Coloring Problems
A Brief Introduction, with Project Ideas

Last revision: December 2, 1992

This a work in progress, intended as a quick introduction to the clique and coloring problems, not an exhaustive survey. (More complete surveys and bibliographies are listed in the references, some of them available via anonymous FTP from dimacs.rutgers.edu.) Here we restrict our attention to key references (the set of which may change as the document evolves). Feel free to send us any suggested additions or clarifications, or additional project suggestions. The email address for suggestions is challenge@dimacs.rutgers.edu.

• Introduction
• Sample Applications
  • Time Tabling and Scheduling
  • Frequency Assignment
  • Register Allocation
  • Printed Circuit Board Testing I - Coloring
  • Printed Circuit Board Testing II - Clique
  • Pattern Matching
  • Analysis of Biological and Archeological Data
• Solution Approaches
  • Cliques
  • Coloring
• Suggested Research Projects
• References
• About this document ...