Of course, we can only cut along diagonals which are part of the triangulation. For each one of them (name it ~d~), we must check if it separates two triangles of the same color. Let's look at one of the colors, ~c~. If we take the vertices of all triangles colored in ~c~, ~v^c_1 < v^c_2 < \dots < v^c_{k(c)}~, then ~d~ can not cross any diagonal ~(v^c_i, v^c_j)~. But if it crosses some such diagonal, then it also crosses some diagonal ~(v^c_i, v^c_{i+1})~ (where ~v^c_{k(c)+1} = v^c_1~). When we realize that:

$$\displaystyle \sum_{i=1}^n k(i) \le 3n-6$$

then we see that we have a solution running in ~\mathcal O(n^2)~.

Now we can add a data structure improvement. If we keep a two dimensional tree containing all diagonals ~(v^c_i, v^c_{i+1})~, where each node of the first dimension tree contains a tree with ends of the diagonals which begin in a specified (for that particular node) segment. That kind of structure gives us chance to check if ~d~ crosses any of the diagonals in time ~\mathcal O(\log^2 n)~, which gives ~\mathcal O(n \log^2 n)~ in total.

There is another way to look at the problem, which gives even better results. We can observe that the graph, in which vertices represent triangles and there is an edge between vertices if the corresponding triangles share an edge, is a tree. Then the problem is to cut some of the edges of a tree not to separate vertices with the same color. Let's take the vertices of some color, find the lowest common ancestor of all these vertices and write the number of these vertices in the ancestor. Now, after doing that for each color, we have enough data to determine if an edge can be cut. More specifically: an edge cutting off a subtree can be cut, if the sum of the numbers written in all vertices of the subtree is equal to the number of vertices in the subtree. This leads to an algorithm with runtime ~\mathcal O(n \log n)~ (or even better, if we solve the LCA problem optimally).