<p>A recent paper by Custic, Klinz, Woeginger "Geometric versions of the three-dimensional assignment problem under general norms", Discrete Optimization 18: 38-55 (2015) contains (and proves) the following proposition:</p>

<blockquote>
  <p><strong>Proposition 5.1:</strong> Partition into triangles on 6-regular tripartite graphs is NP-complete.</p>
</blockquote>

<p>Now just follow the reduction in the proof with a NO-instance, and you will get a 6-regular tripartite graph on $3q$ vertices that cannot be partitioned into $q$ triangles.</p>

CC BY-SA 3.0
2016-03-10T18:19:41.703Z
2016-03-10T18:19:41.703Z
Gamow
<p>Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that:</p>

<ol>
<li>$|X|=|Y|=|Z|=q$.</li>
<li>$2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v.</li>
<li>$\sum_{x \in X} d(x)=\sum_{y \in Y}d(y)=\sum_{z \in Z} d(z)$</li>
</ol>

<p>Can we partition $G$ into $q$ vertex-disjoint triangles?</p>

<graph-theory><graph-colouring>
Partition into triangles in a 3-partite graphe
Farah Mind
# Partition into triangles in a 3-partite graphe

(Asked by: username_0 on 2016-03-10)

Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that:

1. $|X|=|Y|=|Z|=q$.
2. $2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v.
3. $\sum\_{x \in X} d(x)=\sum\_{y \in Y}d(y)=\sum\_{z \in Z} d(z)$

Can we partition $G$ into $q$ vertex-disjoint triangles?

**Tags:** graph-theory, graph-colouring

---

## 1 answers

### Answer by username_1 on 2016-03-10. Score: 7 | Accepted answer

A recent paper by Custic, Klinz, Woeginger "Geometric versions of the three-dimensional assignment problem under general norms", Discrete Optimization 18: 38-55 (2015) contains (and proves) the following proposition:

> **Proposition 5.1:** Partition into triangles on 6-regular tripartite graphs is NP-complete.

Now just follow the reduction in the proof with a NO-instance, and you will get a 6-regular tripartite graph on $3q$ vertices that cannot be partitioned into $q$ triangles.


---

