Haemers Bound

I just read a couple of papers of Haemers from 1979, who introduced a minimum rank upper bound for the Shannon capacity of a graph and, hence, the independence number. Importantly, it can be better than Lovasz’s theta function.

Let G be a graph and B be an nxn matrix with Bi,j=0 iff there is an edge from vertex i to vertex j in G. Then alpha is no more than the rank of B. And, thus, alpha is no more than the minimum rank of all matrices of this form. He gives examples of computations of this bound in special cases. As far as I know it can’t be computed efficiently in the general case – although I’d love to know an algorithm.