Particionamento e Extensão de Grafos Cordiais em Conjuntos Independentes e Cliques

 Este trabalho descreve um estudo sobre particionamento em grafos. Estudamos os grafos-(lc, L), grafos cujo conjunto de vértices pode ser particionado em k conjuntos independentes e 1 cliques. Este problema é uma generalização natural do problema de reconhecer grafos split, e é NP-completo para grafos em geral, a menos que lc 5 2 e 1 5 2. Apresentamos um teorema de caracterização de grafos cordais-(k, 1) por subgrafos induzidos e algoritmos eficientes para reconhecimento desta classe de grafos. Além disso, consideramos partições gerais para a classe dos grafos cordais. Para cada matriz simétrica h!! definida sobre 0,1, *, o problema da M-partição procura por uma partição do grafo de entrada em conjuntos independentes, cliques, ou conjuntos arbitrários, com algumas exigências entre alguns pares de conjuntos, por exemplo, que sejam completamente adjacentes ou que não possuam nenhuma aresta entre eles, tal como especificado na matriz M. Tais partições generalizam o problema da coloração de grafos e o problema do homomorfismo, e aparecem frequentemente na teoria de grafos perfeitos. Mostramos que muitos problemas de Ad-partição que são NP-completos em geral tornam-se polinomiais quando restritos à classe dos grafos cordais, mesmo na presença de listas. Por outro lado, mostramos que existem problemas de M-partição que permanecem NP-completos mesmo para grafos cordais.