Partition and Extension of Chordal Graphs into Independent Sets and Cliques - Nogueira, Loana Tito; Klein, Sulamita; Protti, Fábio (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2004)
Estudamos os grafos-(k, l), grafos cujo conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques. O reconhecimento de grafos-(k, l) é NP-completo para k ≥ 3 ou l ≥ 3. Caracterizamos e reconhecemos polinomialmente os grafos cordais-(k, l). Além disso, consideramos M-partições gerais para esta mesma classe. Para cada matriz simétrica M definida sobre 0, 1, ∗, o problema da M-partição procura por uma partição dos vértices do grafo em conjuntos independentes, cliques, ou conjuntos arbitrários, exigindo-se todas as arestas (ou nenhuma) entre pares de conjuntos, tal como codificado na matriz M. Mostramos que muitos desses problemas de partição tornam-se polinomiais para grafos cordais mesmo na presença de listas.