In 1979, L. Lovasz defined the theta number, a spectral/semidefinite upper bound on the stability number of a graph, which has several remarkable properties (e.g. it is exact for perfect graphs). The definition of Lovasz's theta number relies on the notion of orthonormal representation of the graph, and, dually, can be obtained by optimizing over the theta body. In the paper we will describe counterparts of theorems due to Wilf, Hoffman, and Lovasz; three spectral and one semidefinite bound on the stability number, obtained via optimizing over a polyhedron of nonnegative matrices, resp. the inverse theta body.
Article
View Four new upper bounds for the stability number of a graph