Iterative coloring extension of a maximum clique

In this paper we present an improved branch and bound algorithm for the ver tex coloring problem. The idea is to try to extend the coloring of a maximu m clique to its adjacent vertices. If this succeeds. its successive neighbo rs are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optima l coloring of this subgraph by branch and bound. The process is repeated it eratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the m aximum clique search, and a new method to compute upper bounds on subgraphs . Furthermore, a new branching rule and a method for the selection of the i nitial maximum clique are presented. Extensive computational results and co mparisons with existing exact coloring algorithms on random graphs and benc hmarks are given. (C) 2001 John Wiley & Sons, Inc.