Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several meta-heuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem.