H-Partições de Grafos

Sejam G e H grafos simples e não direcionados. Este trabalho considera o problema de encontrar, se houver, uma partição P={S_1,S_2,...,S_k} de V(G) de modo que exista uma bijeção entre P e V(H) satisfazendo a seguinte propriedade: se cada S_i é associado a v_i em V(H), então v_i é adjacente (resp., não adjacente) a v_j se e somente se S_i é completamente adjacente (resp., completamente não adjacente) a S_j. Se tal partição existe então dizemos que G possui uma H-partição. O foco deste trabalho é desenvolver métodos de reconhecimento de H-partições de um grafo e determinar algumas classes de grafos em que a solução para o Problema da H-Partição pode ser obtida em tempo polinomial.