Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is minimized.
For example, a cut with 1 blue edge, 1 red edge, and 1 yellow edge between $V_1$ and $V_2$ is worst than a cut with 10 blue edges and 15 red edges between $V_1$ and $V_2$.
Of course, the uncolored cut is well-known to be polynomial-time solvable. The complexity of this colored version is reported as an open-problem in http://hal.archives-ouvertes.fr/hal-00371100/en. It surprise me. Do I miss some known result?