Una camarilla de un gráfico no dirigido es, en teoría de grafos , un subconjunto de los vértices de este gráfico cuyo subgrafo inducido es completo , es decir, dos vértices cualesquiera de la camarilla son siempre adyacentes.
Una camarilla máxima de un gráfico es una camarilla con la mayor cardinalidad (es decir, tiene el mayor número de vértices). La cardinalidad de tal camarilla máxima es una característica del gráfico, llamado número de camarilla , y que podemos relacionar con su número cromático . El problema de la camarilla máxima, encontrar una de las camarillas máximas para un gráfico dado (finito), es un problema NP-difícil .
En teoría de grafos , una camarilla es un conjunto de vértices adyacentes de dos por dos. Pero el término "clic" también se usa a menudo para referirse al gráfico inducido por una camarilla, es decir, un subgráfico inducido completo .
Asimismo, el término "biclical" se usa comúnmente para designar un gráfico bipartito completo en lugar de su conjunto de vértices o aristas.
A veces usamos el término p-clique o incluso clique de cardinalidad p para denotar un clique que contiene p vértices.
El número cromático de un gráfico es mayor o igual que el número de vértices en su camarilla más grande.
Varios problemas algorítmicos se definen a partir de las camarillas, en particular el problema de la camarilla y el problema de la partición de la camarilla , que son parte de los 21 problemas NP-completos de Karp .
(en) Ke Xu, " Puntos de referencia con soluciones óptimas ocultas para problemas de gráficos (grupo máximo, conjunto independiente máximo, cobertura de vértice mínima y coloración de vértice " , en BUAA