Variable space search for graph coloring Original Research Article

Let image be a graph with vertex set image and edge set image. The image-coloring problem is to assign a color (a number chosen in image) to each vertex of image so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the image-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The image-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.