Sobre la N+-perfección de los grafos quasi-line.

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; WAGLER, ANNEGRET

Santa Fe

Congreso; LXIV Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2015

Unión Matemática Argentina

En el presente trabajo se estudia el operador N+ denido por Lovasz-Schrijver [?] sobre la relajacion por arcos ESTAB(G) del poliedro de conjuntosestables STAB(G) de un grafo G. Este operador combina restriccioneslineales con restricciones no lineales provenientes del cono de las matricessemidenidas positivas y se ha demostrado su eciencia para resolver el problemadel conjunto estable de maximo peso sobre los grafos para los cualesN+(ESTAB(G)) = STAB(G).Nuestro interes esta enfocado en el problema de caracterizar los grafosG para los cuales se consigue el poliedro de los estables en G en tansolo una iteracion del operador N+, es decir los grafos G para los cualesN+(G) := N+(ESTAB(G)) coincide con STAB(G). Recientemente, estos grafos hansido llamados grafos N+-perfectos y, en la busqueda de una descripcion poliedralde STAB(G) para los mismos, se formulo una conjetura que ha sidodemostrada para ciertas clases de grafos como los near-perfectos, los grafosredes y los grafos de línea entre otros. En este trabajo demostramosque la conjetura se cumple para la clase de grafos conocidos comoquasi-line.