M-Partições em Cografos

O problema da M-partição foi inicialmente introduzido por Feder et al. da seguinte forma: seja M uma matriz simétrica (mxm) com valores Mij \in {0, 1, *}. Uma M-partição de um grafo G é uma partição de G em m conjuntos, obedecendo as restrições impostas pelos índices da matriz M, tal que: dados dois vértices distintos, u e v de V (G), alocados nos conjuntos i e j, respectivamente, temos: Se Mij = 0, então (u, v) \in E(G); Se Mij = 1, então (u, v) \in E(G); e Se Mij = *, não podemos afirmar nada sobre a existência ou não da aresta no grafo G. Neste trabalho vamos restringir nossas buscas na subclasse dos cografos e encontrar as obstruções para configuração em que todos os valores da diagonal principal da matriz M são iguais a 0, todas as
restrições da última coluna são iguais a 1 e as demais restrições são *.