Problem podziału na 3 kliki polega na określeniu, czy wierzchołki wykresu, powiedzmy , można podzielić na 3 kliki. Problem ten jest trudny do wyeliminowania przez proste zmniejszenie z 3-kolorowego problemu. Nietrudno dostrzec, że odpowiedź na ten problem jest łatwa, gdy diam ( G ) = 1 lub diam ( G ) > 5 . Problem pozostaje trudny NP, gdy diam ( G ) = 2 przez zwykłą redukcję od siebie (biorąc pod uwagę wykres G , dodaj wierzchołek i połącz go ze wszystkimi innymi wierzchołkami).
Jaka jest złożoność tego problemu dla wykresów z dla 3 ≤ p ≤ 5 ?
źródło