Network Resources for Coloring a Graph

by: Michael Trick (

Last Update: October 26, 1994


Given an undirected graph, a clique of the graph is a set of mutually adjacent vertices. A maximum clique is, naturally, a clique whose number of vertices is at least as large as that for any other clique in the graph. If the vertices have weights then a maximum weighted clique is a clique with the largest possible sum of vertex weights.

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


Solution Codes

Test Instances

People and Papers