Let G=(V,E) be a graph with vertex set V and edge set E. The graph coloring problem consists of assigning an integer (called color) to each vertex so that adjacent vertices get different colors, and the total number of different colors is minimized. The adaptive memory algorithm is a hybrid evolutionary heuristic based on a central memory. At each generation, the idea is to use the information of a central memory for producing an offspring which is then improved by using a local search algorithm. The solution thus obtained is finally used to update the information contained in the memory. We propose an adaptive memory algorithm for the graph coloring problem. The results obtained so far give evidence that our method is competitive with the best known coloring algorithms.

We introduce a new approach to solve the maximum clique problem, which is the result of the combination of two concepts. The first is a general decomposition method restricting the search for a maximum clique to subgraphs, but also performing an exhaustive search of the graph. The second is a heuristic method, based on the concepts of penalty and evaporation, which identifies a large clique in a graph in a very short computing time.

The struction method is a general approach to compute the stability number of a graph based on step-by-step transformations each of which reduces the stability number exactly by one. In the present paper we review the principal results on this topic and propose a generalization of the method. We also discuss its relationship with some other known graph transformations, as well as the possibility to use stability preserving transformations to increase the efficiency of this approach.

2- and 3-dimensional bin packing problems have been widely studied in the OR literature as they have important practical applications. A few recent papers dealt with the computation of lower bounds on the minimum number of bins (rectangles or cubes) needed to pack a given set of items (rectangles or parallelepipeds). In this paper, we study the lower bounds that can be derived from the compatibility relations between items, which are naturally represented by an undirected graph.