# SDP and chromatic number upper bounds

Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?

• "outer bounds" ? also, are you referring to the Lovasz theta function ? – Suresh Venkat Dec 23 '11 at 7:08
• @Suresh: Here by outer bound, I imply upper bound and by inner bound, I imply lower bound. I thought Lovasz theta is only for outer bounding the independence number? Would it apply to chromatic number as well? Since chromatic number is implicitly a minimal number under some constraints, I am curious if there are any Lovasz type outer bounds to chromatic number and Lovasz type inner bounds for independence number as well? – v s Dec 23 '11 at 15:50
• You might want to edit to use the more standard terminology ? (at least standard in algorithms) – Suresh Venkat Dec 23 '11 at 16:15
• @SureshVenkat done – v s Dec 23 '11 at 16:39

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.
• in the Laserre hierarchies paper (cs.princeton.edu/~rongge/LasserreColoring.pdf) there are some references for integrality gap results: look at references 14, and 15. Also Mario Szegedy showed the Lovasz theta has integrality gap $n^{1-\epsilon}$ w.r.t. independence number if and only if it has integrality gap $n^{1-\epsilon}$ w.r.t. the chromatic number (cs.rutgers.edu/~szegedy/PUBLICATIONS/theta.ps). Alon and Kahale show an integrality gap of $n^{1-\epsilon}$ for any $\epsilon$ for Lovasz theta w.r.t. independent set. I am not an expert, follow refs in these papers. – Sasho Nikolov Dec 23 '11 at 22:10