1
$\begingroup$

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 property applies recursively to all induced subgraphs of V1 and V2

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: this is an example graph with the given properties. I need to find the bold triangle

Blue boxes symbolize the partitions are fully connected, purple boxes mean no connection between the partitions There is no connection between the coloring of nodes and the partitions, also the partitions have to be computed on the fly

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.