Source author record

M. Escalante

M. Escalante appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.OC

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Characterizing N+-perfect line graphs

The subject of this contribution is the study of 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 graphs are cliques and odd holes.

preprint2015arXiv

Lift-and-project ranks of the stable set polytope of joined a-perfect graphs

In this paper we study lift-and-project polyhedral operators defined by Lov?asz and Schrijver and Balas, Ceria and Cornu?ejols on the clique relaxation of the stable set polytope of web graphs. We compute the disjunctive rank of all webs and consequently of antiweb graphs. We also obtain the disjunctive rank of the antiweb constraints for which the complexity of the separation problem is still unknown. Finally, we use our results to provide bounds of the disjunctive rank of larger classes of graphs as joined a-perfect graphs, where near-bipartite graphs belong.

preprint2014arXiv

Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

We study the Lovász-Schrijver lift-and-project operator ($LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $LS_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of $LS_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among $LS_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.