Cografos-(K,L): Caracterização e Reconhecimento

Neste trabalho, consideramos o problema de particionar um grafo em k conjuntos independentes e 1 cliques, conhecido como o problema da (k, 1)- partição ou o problema dos grafos-(k, I), o qual foi introduzido por Brandstadt, e generalizado por Feder, Hell, Klein e Motwani como o problema da Mpartição. Brandstadt provou que, dado um grafo G, é NP-completo decidir se G é um grafo-(k, I) para k > 3 ou I > 3. Em particular, consideramos uma subclasse de grafos perfeitos: os cografos, que consistem de grafos sem P4 (caminho induzido com 4 vértices), e apresentamos uma caracterização dos cografos-(k, I) em termos de subgrafos proibidos, i. e., obstruções, além de um algoritmo linear para reconhecer tal classe. O algoritmo linear baseia-se no fato de que cliques máximas e conjuntos independentes máximos podem ser encontrados em tempo linear quando restritos a cografos..