# 3-Clique Partition for graphs of fixed diameter

The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-colorability problem. It is not hard to see that the answer to this problem is easy when $\textrm{diam}(G) = 1$ or $\textrm{diam}(G) > 5$. The problem remains NP-hard when $\textrm{diam}(G) = 2$ by a simple reduction from itself (given a graph $G$, add a vertex and connect it to all other vertices).

What is the complexity of this problem for graphs with $\textrm{diam}(G) = p$ for $3\le p \le 5$?

The problem seems to be in $P$.
Take two vertices $u$, $v$ with distance exactly 3 (such a pair must exist when $p\ge 3$). They must have different colors (I will use R, G, B to denote 3 colors and the vertices in the same clique are colored the same color). Wlog assume $u$ is colored Red and $v$ is colored Green.
Now the rest of the vertices are partitioned into 3 sets: $\Gamma(u)$ (neighbors of $u$), $\Gamma(v)$ and $V-\Gamma(u)-\Gamma(v)$. The third set must be colored Blue because they are adjacent to neither $u$ nor $v$. Neighbors of $u$ must be colored either Red or Blue because they are not adjacent to $v$, similarly neighbors of $v$ must be colored either Green or Blue. Each vertex now has at most two choices, therefore the problem becomes a 2-SAT instance that we can solve in polynomial time.
• Let $B(v)$ be true if and only if we color vertex $v$ blue. Consider two vertices $u$ and $v$ not connected by an edge. Assume both of them can be blue or red. You must have the following clauses in your 2-SAT instance: $(B(v) \vee B(u))$ and $(\bar{B(v)} \vee \bar{B(u)})$. The other case that one of them can be blue or red and the other one blue or green is similar (you just need one clause). Mar 4, 2012 at 5:55