<p>The problem seems to be in $P$.</p>

<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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-03T04:52:38.430Z
can you describe corresponding  2-SAT formulation?
user5153
CC BY-SA 3.0
2012-03-04T05:55:12.927Z
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).
randomizer
CC BY-SA 3.0
2012-03-02T14:25:42.747Z
2012-03-02T14:25:42.747Z
Rong Ge
<p>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) &gt; 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).</p>

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

<cc.complexity-theory><graph-theory><np-hardness><clique>
3-Clique Partition for graphs of fixed diameter
randomizer
# 3-Clique Partition for graphs of fixed diameter

(Asked by: username_0 on 2012-03-01)

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

**Tags:** cc.complexity-theory, graph-theory, np-hardness, clique

---

## 1 answers

### Answer by username_1 on 2012-03-02. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: can you describe corresponding  2-SAT formulation?  
> **username_0**: 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).  

---

