Characterizing N+-perfect line graphs

Article

Authorship:

ESCALANTE, MARIANA SILVINA ; NASINI, GRACIELA LEONOR ; Wagler, Annegret Katrin

Date:

2017

Publishing House and Editing Place:

Wiley

Magazine:

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, vol. 24 (pp. 325-337) Wiley

Summary

The aim of this paper is to study the Lovász-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 subgraphs are cliques and odd holes.

Key Words

LINE GRAPHSN+-PERFECT GRAPHSSTABLE SET POLYTOPEPSD RELAXATION

Download or request the full text:

http://hdl.handle.net/11336/52511