The Voronoi diagram of a set of points is the dual graph of the Delaunay triangulation of the points. The Voronoi regions for p,q share an edge if and only if p,q have a Delaunay edge between them.

This means that questions about Voronoi region adjacency can be more conveniently framed as questions about adjacency/connectivity in a plain graph, if you have both structures available as well as the correspondence between the two. In terms of your sets of points, if some Delaunay edge has its two endpoints in the same set/grouping, then you would have colored those two Voronoi regions the same, and you can throw out the dual edge (this is the edge in the Voronoi diagram that the two regions share).

Following this Delaunay-adjacency idea through, you can compute in the Delaunay graph the "contiguous" components (there's probably a better name for this -- I just made it up). In other words, partition the Delaunay graph into maximal connected subgraphs whose vertices are all in the same set (starting at each unseen vertex, traverse with BFS/DFS only to neighbors in the same set as the root). These partitions will correspond exactly to the polygons you want. You can take each contiguous component, and traverse around its perimeter, accumulating the border Voronoi edges. If removing a particular component disconnects the Delaunay graph into k components, then the corresponding compound Voronoi polygon will have k-1 holes, so you'd need to traverse those perimeters as well (although the perimeters are shared by other components and traced out there too).