Проблема разбиения с 3-мя кликами - это проблема определения , можно ли разбить вершины графа, скажем, , на 3 клики. Эта проблема является NP-трудной из-за простого сокращения проблемы 3-окрашиваемости. Нетрудно видеть, что ответ на эту проблему прост, когда diam ( G ) = 1 или diam ( G ) > 5 . Проблема остается NP-трудной, когда diam ( G ) = 2 простым сокращением от себя (для графа G добавьте вершину и соедините ее со всеми остальными вершинами).
Какова сложность этой задачи для графов с при 3 ≤ p ≤ 5 ?
источник