Lovász-Schrijver SDP-operator and a superclass of near perfect graphs

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; TUNÇEL, LEVENT

Playa del Carmen

Simposio; LAGOS 2013- VII Latin American Algorithms, Graphs and Optimization Symposium; 2013

We study the Lovász-Schrijver SDP-operator applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the SDP-operator generates the stable set polytope in one step has been open since 1990. In an earlier publication, we named these graphs N_+-perfect. In the current contribution, we propose a conjecture on combinatorial characterization of N_+-perfect graphs and make progress towards such a full combinatorial characterization by establishing a new, close relationship among N_+-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.