Problemas Sanduíche em Grafos: Classes Hereditárias e Partições

Problemas sanduíche são generalizações de problemas de reconhecimento de uma propriedade ¦. Enquanto em problemas de reconhecimento comum existe apenas um grafo como entrada, em problemas sanduíche existem dois grafos e procura-se por um terceiro grafo, intermediário entre os dois grafos de entrada, satisfazendo a propriedade II. Esta tese apresenta resultados sobre dois tipos distintos de propriedades de grafos. O primeiro tipo trata-se de classes hereditárias de grafos, com ênfase a classes relacionadas à propriedade Helly. O segundo tipo trata-se de problema de partições dos vértices de um grafo. Apresentamos uma dicotomia polinomial para os problemas departição em três partes não vazias.