3-Clique Partition for graphs of fixed diameter

Question

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$?

Answer 1

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.