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.
Both of these problems are formally NP-hard for general graphs
[41]. It therefore seems unlikely that it will be possible
to find a fast (i.e. polynomial-time) algorithm to solve these
problems. In fact, based on the results of
[66][5][6][35] it seems unlikely that it is even
possible to find an approximate solution to these problems quickly:
Assuming P 
NP, there is an 
such that no
polynomial time approximation algorithm for either problem can find a
solution that is guaranteed to be within a ratio of 
of
optimal.
Despite these negative results, it is still necessary to find solutions to large clique and coloring problems. The applications do not go away just because the problem is intractable in the worst case. Therefore, it is important for us to determine how difficult clique problems are to solve in practice. Do hard instances, or at least hard-to-approximate instances, only occur rarely? What structural properties of instances make it difficult to solve these problems, and how can those structures be avoided? The purpose of this note (which is currently an evolving document) is to outline some past research on solving clique and coloring problems and to identify some possible research directions.
In the next section, we discuss a few typical applications of the maximum clique and minimum coloring problems. In section 3, we discuss several solution approaches that have been tried in the past. In section 4 we talk about some suggested research directions.