Near-perfect graphs with polyhedral N+(G)

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

Bariloche

Simposio; LAGOS 2011- VI Latin American Algorithms, Graphs and Optimization Symposium; 2011

One of the beautiful results due to Groetschel, Lovász and Schrijver is the fact that the theta body of a graph G is polyhedral if and only if G is perfect. Related to the theta body of G is a foundational construction of an operator on polytopes, called N+(·), by Lov´asz and Schrijver. Here, we initiate the pursuit of a characterization theorem analogous to the one above by Groetschel, Lovász and Schrijver, replacing the theta body of G by N+(G) and searching for the combinatorial counterpart to replace the class of perfect graphs.