  We consider semidefinite relaxations of Stable-Set and Coloring, which are
based on quadratic 0-1 optimization. Information about the stability number and
the chromatic number is hidden in the objective function. This leads to
simplified relaxations which depend mostly on the number of vertices of the
graph. We also propose tightenings of the relaxations which are based on the
maximal cliques of the underlying graph. Computational results on graphs from
the literature show the strong potential of this new approach.
