Sandwich Problems and Structural Properties of the Two Forbidden Four-vertex Subgraphs Classes

Palestrante: Jose Alvarado, UFF.

Data: 26 de outubro de 2016, 11h.

Local: Sala 409, Bloco H, IME, Campus Gragoatá, UFF.

Resumo: The \Pi Graph Sandwich Problem (GSP) introduced by Golumbic and Shamir in 1993, asks, for a pair of graphs G^1= (V, E^1), G^2 = (V, E^2) with E^1 \subseteq E^2, whether there exists a graph G = (V, E) that satisfies property \Pi and E^1 \subseteq E \subseteq E^2.

The GSP have attracted much attention because of many applications and so several sandwich problems were considered for different graph classes, for instance: interval graph, unit interval graph, permutation graph and comparability graph sandwich problems are all NP-complete, while the split graph, threshold graph and cograph sandwich problems are in P.

Dantas et al. (2011, 2015) completely classify the complexity of the F-free GSP when F is a four-vertex subgraph. Motivated by a question proposed by M. C. Golumbic about the complexity status of the GSP of the well known trivially perfect graph class, we study several two forbidden four-vertex graph classes and determine that: {C_4,P_4}-free (trivially perfect), {\overline{claw},P_4}-free, {\overline{paw},P_4}-free, {diamond,P_4}-free, {diamond,K_4}-free, {diamond,C_4}-free, {diamond,paw}-free, {C_4,paw}-free, {claw,paw}-free, {\overline{claw},paw}-free, {\overline{paw},paw}-free, {4K_1,K_4}-free, {\overline{claw},claw}-free and {C_4,2K_2}-free graphs are all in P, while the {K_4,C_4}-free, {K_4,paw}-free, {4K_1,paw}-free and {2K_2,paw}-free graphs are NP-complete. In addition, we show structural properties for several two forbidden four-vertex subgraphs classes.

Observações: Jose Alvarado é aluno de doutorado da Pós-graduação em Matemática da UFF, orientado pela profa. Simone Dantas. Este trabalho foi aceito para apresentação no Workshop Lawcg 2016.