Classes de Grafos Clique-Inversos

Uma clique maximal é um subconjunto de vértices de um grafo completamente conectados entre si por arestas de tal modo que não existe mais nenhum outro vértice do grafo que esteja conectado a todos os vértices do subconjunto. Dado um grafo G, o grafo de intersecção das cliques maximais de G é o grafo clique K(G) de G. Denominamos K como o operador clique.  O objetivo desta tese é considerar o seguinte problema: Fixada uma classe C de grafos, que propriedades possui a classe constituída pela imagem inversa de C pelo operador clique? Esta nova classe é denominada classe dos grafos clique-inversos dos grafos C. Entre os resultados desta tese, caracterizamos grafos clique-inversos de: Grafos com tamanho máximo de clique três, grafos livres de triângulos, grafos bipartidos, grafos bipartidos cordais e árvores. O reconhecimento destas classes pode ser feito em tempo polinomial. Mostramos que, para k fixo, o problema de decidir se K(G) tem uma clique de tamanho maior ou igual a k pode ser resolvido em tempo polinomial. Tratamos também de classes de grafos clique-inversos onde o problema de reconhecer se um dado grafo G pertence a uma destas classes é NP-difícil. Provamos que os problemas de reconhecimento das classes a seguir são Co-NP-completos: grafos clique-inversos de grafos cordais, co-cordais, de partição, co-bipartidos, co-bipartidos-cordais, de intervalo, de co-intervalo, de comparabilidade, de co-comparabilidade, de permutação, livres de TA e bloco. Mostramos também que os problemas de decidir o número cromático e o número de estabilidade de K(G) são NP-completos.