El operador clique y los grafos planares

Abstract

Se llama completo de un grafo a un conjunto de vértices adyacentes entre sí; si un completo es maximal con respecto a la inclusión, se dice que es un clique del grafo. Los cliques son estructuras especiales que naturalmente han despertado interés desde el mismo inicio de la Teoría de Grafos. Varios problemas famosos, como por ejemplo el problema de coloración de un grafo, o el problema de satisfabilidad de una fórmula lógica, se han vinculado y formulado en términos de los cliques de un grafo. Por otro lado, existe una gama de problemas motivados en el propio estudio de los cliques de un grafo. Particularmente haremos foco en el estudio del grafo que muestra la relación de intersección entre estos cliques: el grafo clique. Dado un grafo G obtenemos el grafo clique de G considerando un vértice por cada clique de G y haciendo dos vértices adyacentes si los correspondientes cliques tienen intersección no vacía. De esta simple definición surgen inmediatamente varias preguntas; las siguientes tres son las que han dado origen a las tres principales líneas de investigación: ¿Todo grafo es el grafo clique de algún grafo? Dada una clase particular de grafos, ¿cómo es la clase formada por los grafos clique de los grafos dados? El proceso, que partiendo de un grafo dado obtiene iterativamente el grafo clique del grafo clique, ¿es convergente o genera una secuencia infinita de distintos grafos?