El problema de la partición de 3 cliques es el problema de determinar si los vértices de un gráfico, digamos , se pueden dividir en 3 camarillas. Este problema es NP-duro por una simple reducción del problema de 3 colorabilidad. No es difícil ver que la respuesta a este problema es fácil cuando diam ( G ) = 1 o diam ( G ) > 5 . El problema sigue siendo NP-duro cuando diam ( G ) = 2 por una simple reducción de sí mismo (dado un gráfico G , agregue un vértice y conéctelo a todos los demás vértices).
¿Cuál es la complejidad de este problema para gráficos con para 3 ≤ p ≤ 5 ?
fuente