Theoretical Consideration

How different (harder) is the colored graph isomorphism problem from the uncolored graph isomorphism problem? Clearly, the uncolored graph isomorphism problem is a special case of the colored one: if and are two uncolored graphs, then we can always assign to every vertex and every edge the same color which transfers the pair of graphs into a pair of color graphs.  This does not change the essence of the problem since the color is identical to all edges and vertices of both graphs.
Surprisingly, the colored graph isomorphism problem can be reduced to the uncolored graph isomorphism problem by a suitable transformation of the input colored graphs into corresponding uncolored graphs.  First, notice that if the colors used for one graphs are different from that of the other graphs, then the graphs are non-isomorphic.  Furthermore, we can assume that the colors used for vertices are different from the colors used for edges.
We can always start solving the isomorphism problem by checking if the list of colors used for one graph is identical to that for the other.  The transformation described on this page is executed after this checking is done.  Then, we transform every labeled graph into an unlabeled graph and see if the resulting uncolored graphs are isomorphic.  Then and only then are the initial colored graphs isomorphic.

Illustration to the procedure Transformation

In the left part of the figure, it is shown that the vertex labeled with N (resp. O) is replaced with an unlabeled vertex adjacent to two (resp. three) new vertices; the new vertices are of degree one each.  Every edge showing a double link is replaced with a new vertex adjacent to the vertices that were connected by the edge.  Every vertex replacing a double link is made adjacent to an additional new vertex of degree one.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.