Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques

Abstract

Neste trabalho consideramos a seguinte generalização de grafos split: Um grafo G é um grafo-(k; l) se seu conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques (uma clique é um subgrafo completo não necessariamente maximal). Portanto, os grafos-(k; l) são uma generalização dos grafos split, que correspondem aos grafos-(1; 1). Grafos split podem ser eficientemente reconhecidos [4]. Além disso, os problemas clássicos de otimização combinatória são também resolvidos eficientemente nessa classe. Na verdade, nosso resultado principal é uma caracterização de grafos cordais-(k; l). Também apresentamos um algoritmo para reconhecer grafos cordais-(k; l) cuja complexidade é O(n(m + n)). Quando k = l = 1, nosso algoritmo possui complexidade O(m + n). Em particular, obtivemos um algoritmo mais simples e eficiente apra reconhecer grafos split, do qual torna-se fácil derivar a conhecida caracterização de grafos split por subgrafos proibidos.