SDP and chromatic number upper bounds Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?
SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see wiki). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the objective of the SDP by $U$ and you'll get an upper bound as well. However, there exist graphs for which the Lovasz theta gives a lowerbound of $k = O(1)$ and the chromatic number is at least $n^{1 - 2/k}$. There is some hope that higher levels of the Lasserre hierarchy can give stronger relaxations. However, notice that chromatic number is  hard to approximate within $n^{1 - \epsilon}$ (see this) in general (i.e. if you're not just interested in the promise problem where the yes instance has constant chromatic number). So, for any SDP, integrality gaps better than $n^{1-\epsilon}$ will either be restricted to cases where the SDP relaxation has  constant value or will be nonconstructive (i.e. superpolynomial time rounding or superpolynomial size relaxation), unless P=NP.