Lift-and-project ranks of the stable set polytope of joined a-perfect graphs

摘要

In this paper we study lift-and-project polyhedral operators defined byLov?asz and Schrijver and Balas, Ceria and Cornu?ejols on the clique relaxationof the stable set polytope of web graphs. We compute the disjunctive rank ofall webs and consequently of antiweb graphs. We also obtain the disjunctiverank of the antiweb constraints for which the complexity of the separationproblem is still unknown. Finally, we use our results to provide bounds of thedisjunctive rank of larger classes of graphs as joined a-perfect graphs, wherenear-bipartite graphs belong.