A sequential elimination algorithm for computing bounds on the clique number of a graph

AbstractWe consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bound on the clique number of a graph, we present a sequential elimination algorithm which is guaranteed to improve upon that upper bound. Computational experiments on DIMACS instances show that, on average, this algorithm can reduce the gap between the upper bound and the clique number by about 60%. We also show how to use this sequential elimination algorithm to improve the computation of lower bounds on the clique number of a graph