Complexity of Haemers' minimum rank In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph".

Tims has a survey of more recent results his thesis.

What is the computational complexity of computing Haemmer's minimum rank function?
Computing min rank is NP-hard:


Rene Peeters, "Orthogonal Representation over Finite Fields and the Chromic Numbr of Graphs", 1996.
Salim Y. El Rouayheb, Mohammad Asad R. Chaudhry, Alex Sprintson, "On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks", 2007.