Network Resources for Coloring a Graph

Last Update: October 26, 1994

Introduction

A (vertex) coloring of an undirected graph is an assignment of a label to each node. It is required that the labels on the pair of nodes incident to any edge be different. A minimum coloring of a graph is a coloring that uses as few different labels as possible.

Clique and coloring problems are very closely related. It is straightforward to see that the size of the maximum clique is a lower bound on the minimum number of labels needed to color a graph.

Many problems of practical interest can be modeled as clique and coloring problems. The general form of these applications involves forming a graph with nodes representing items of interest. An edge connects two ``incompatible'' items. The maximum clique problem is then to find as large a set of pairwise incompatible items as possible. The minimum coloring problem is to assign a color to each item so that every incompatible pair is assigned different colors.

This document tries to bring together the various resources that are available on the Internet to help in formulating and solving coloring problems.

This work began with the Second DIMACS Challenge, and many of the items in this report were first collected there. The purpose of this report is to expand on those items and provide a mechanism for further additions to that work.

A Brief Survey of Applications and Algorithms

Last revision: November 3, 1994

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 me any suggested additions or clarifications, or additional project suggestions. The email address for suggestions is trick+@cmu.edu. The Postscript form is also available.

• 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 ...

Bibliographies

• This is the Bibtex format annotated bibliography for cliques and coloring.
• Joe Culberson has put together a very extensive bibliography for graph coloring.

Solution Codes

• I have put together a simple version of a code similar to DSATUR. Here is source code. While probably not the fastest code, it provides a reasonable benchmark.
• This is a picture of how the algorithm works.

Test Instances

People and Papers

• Joe Culberson University of Alberta, Graph Coloring.
• A Column Generation Approach to Graph Coloring by Anuj Mehrotra and Michael Trick, where we use fast algorithms for finding weighted independent sets to solve graph coloring problems