Stable sets and polynomials

AbstractSeveral applications of methods from nonlinear algebra to the stable set problem in graphs are surveyed. The most recent work cited was cowritten by A. Schrijver and involves nonlinear inequalities. These yield a procedure to generate facets of the stable set polytope. If a class of graphs has the property that all facets of the stable set polytope can be generated this way in a bounded number of setps, then the stable set problem is polynomially solvable for these graphs. Perfect, t-perfect and h-perfect graphs have this property