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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.