Wheel inequalities for stable set polytopes

We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytope PG of graph G. Each ‘wheel configuration’ gives rise to two such inequalities. The simplest wheel configuration is an ‘odd’ subdivision W of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing for PW. Generalizations arise by allowing subdivision paths to intersect, and by replacing the ‘hub’ of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time.