pith. sign in

arxiv: 1505.04072 · v1 · pith:YCK6X5BNnew · submitted 2015-05-15 · 🧮 math.CO

Characterizing N+-perfect line graphs

classification 🧮 math.CO
keywords graphsperfectlinepolytopestablecharacterizinggraphonly
0
0 comments X
read the original abstract

The subject of this contribution is the study of the Lov\'asz-Schrijver PSD-operator N+ applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which N+ generates the stable set polytope in one step, called N+-perfect graphs. It is conjectured that the only N+-perfect graphs are those whose stable set polytope is described by inequalities with near-bipartite support. So far, this conjecture has been 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 graph the only facet-defining graphs are cliques and odd holes.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.