Let G=(V,E) be a graph with vertex set V and edge set E. The graph coloring problem consists in 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 an 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 so obtained solution is finally used to update the information contained in the memory. In this paper, we propose an adaptive memory algorithm to the graph coloring problem. The results obtained so far give evidence that our method is competitive with the best known coloring algorithms.