The theta function defined by Lovasz is a polynomial time computable function for every graph, via a semi-definite program. This graph parameter is sandwiched between the clique number and the chromatic number. Since thirty years and despite extensive studies, computing the theta number of a perfect graph is the only known way to compute its chromatic number in polynomial time. The purpose of this subject is to strengthen a new approach to Lovasz's theta function, wbich is based upon some convex supersets of semi-definite matrices.

Page mise à jour le 25/01/2013 à 09:15