Edge bi-partitioning, no triangles: complexity?

Question

I've got to find an algorithm to solve a problem for faculty. I'm not requesting solutions (and please don't post any), just read further.

The problem's sentence:

** Given a graph G = (V, E) find 2 sets S1 and S2 of edges of G such that:
   1. S1 ∪ S2 = E
   2. S1 ∩ S2 = ∅
   3. The 2 subgraphs of G formed by S1 and S2 do not contain triangles (triangle = 3 nodes such that they link together 2 by 2)

I've been trying to find an algorithm to solve this in the last 2 days and I think I'm on the right way. For any of you that stumbled upon it before: do you know if this problem has been solved in polynomial time? (and if not, is it NP-complete/NP-hard/NP?)

Thanks in advance, John

Answer 1

Googled a bit more and found it. It's called monochromatic triangle and it's NP-complete.