Characterizing N+-perfect line graphs

ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; WAGLER, ANNEGRET

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Wiley and sons

Lugar: New York; Año: 2017 p. 325 - 337

0969-6016

The subject of this contribution is the study of the Lov´asz-SchrijverPSD-operator N+ applied to the edge relaxation of the stable set polytopeof a graph. We are particularly interested in the problem of characterizinggraphs for which N+ generates the stable set polytope inone step, called N+-perfect graphs. It is conjectured that the onlyN+-perfect graphs are those whose stable set polytope is describedby inequalities with near-bipartite support. So far, this conjecture hasbeen proved for near-perfect graphs, fs-perfect graphs, and webs. Here,we verify it for line graphs, by proving that in an N+-perfect line graphthe only facet-defining graphs are cliques and odd holes.