Summary: The paper reviews some of the existing exact bounds to the maximum clique of a graph and successively presents a new upper and a new lower bound. The new upper bound is – rank , where is the adjacency matrix of the complementary graph, and derives from a formulation of the maximum clique problem in complex space. The new lower bound is (see text for details) and improves strictly the present best lower bound published by H. S. Wilf [J. Comb. Theory, Ser. B 40, 113–117 (1986; Zbl 0598.05047)].
Throughout the paper an eye is kept on the computational complexity of actually calculating the bounds. At the end, the various bounds are compared on 700 random graphs.