Bounding vertex coloring by truncated Multistage branch and bound

In this article we design a truncated enumerative algorithm based on branch and bound rules embedded in a multistage scheme that allows iterative visits of subgraphs. The algorithm is designed to find lower bounds on the chromatic number of graphs, and, by means of simple coloring extension rules, it is often capable of finding optimal solutions. In this issue we obtain a very promising result: our algorithm was able to solve benchmarks DSJC125_5, DSJC125_9, DSJC250_1, DSJR500_1c, and DSJR500_5, which had not previously been solved. Furthermore, we show how our method can be employed in finding upper bounds on the chromatic number, and thus, we compare the upper bound-lower bound gaps so obtained with those achieved by known exact algorithms. The comparison highlights that in more than half of the tested benchmarks the gap obtained by our algorithm was lower than that obtained by a recent branch and cut method and by the well-known DSATUR algorithm. To provide a deeper analysis we finally compare the upper bounds found by the proposed algorithm on the same benchmarks with the best heuristic solutions known in the open literature. Also, in this case, the proposed truncated branch and bound was often able to outperform these heuristic solutions. (C) 2004 Wiley Periodicals, Inc.