title: divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?
body: <p>In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the following conditions apply: either every vertex of V1 is connected to every vertex of V2 or no Vertex of V1 is connected to a vertex of V2 . This applies recursively to all induced subgraphs of V1 and V2</p>
  <p>I can find all triangles in the Graph by multiplying the adjacency matrix with itself three times and step up the nodes corresponding to the non zero entries of the main diagonal. Then I can see if the  nodes of the triangle are colored the right way. O(n^~2,8)! But given the unique properties of the graph I want to find a solution using divide and conquer to find the colored triangle.
  this is an example graph with the given properties. I need to find the bold triangle:
  <a href="https://i.stack.imgur.com/fkhMO.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/fkhMO.jpg" alt="this is an example graph with the given properties. I need to find the bold triangle " /></a>
  Blue boxes symbolize the partitions are fully connected, purple boxes mean no connection between the partitions</p>