Gap, cosum and product properties of the θ' bound on the clique number.

In a paper published in 1978, McEliece, Rodemich and Rumsey improved the Lovasz bound θ for the maximum clique problem. This strengthening has become well known under the name Lovasz-Schrijver bound and is usually denoted by θ'. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound and the actual clique number can be arbitrarily large, we establish homomorphy results for this bound under cosums and products of graphs. In particular we show that for circulant graphs of prime order there must be a positive gap between the clique number and the bound. [ABSTRACT FROM AUTHOR]