Can someone tell a formal definition for this problem: k-disjoint triangle?
Finding $k$ disjoint triangles in a graph means that you color $3k$ vertices with $k$ colors, $\chi_i, 1 \leq i \leq k$ such that for each color $\chi_i$, the graph $G[X_i] \simeq K_3$, where $X_i$ are the three vertices that received color $\chi_i$.
It simply means that you cannot use the same vertex in two different triangles.
This type of problem is often referred to as $K_3$-packing or triangle-packing: You want to &quot;pack&quot; as many triangles as possible in a graph $G$.
The problem is NP-complete even if you are given a tri-partition of the graph, and this problem is called 3-dimensional matching, one of Karp's 21 NP-complete problems.