Procedure Transformation

line 1:

for every edge

line 2:

if is the color of the edge, then

line 3:

replace with a new vertex colored and two new uncolored edges and .

line 4:

enumerate the colors used for the new graph;
let be the list of the colors.

line 5:

for every vertex

line 6:

if is its color, then

line 7:

introduce new uncolored vertices and new uncolored edges , and decolor (remove color )

Practical Consideration:

It is easy to see that the presence of labels that must be preserved by an isomorphic mapping can only speed up the procedures that split the vertices of the graph into subsets (hopefully of size one).  Firstly, we can start the splitting with the non-trivial partitioning of the vertices according to their labels.  Secondly, we can iterate the splitting by counting the number of edges with a given label (for all labels) connecting the vertex to a given partition.  Clearly, the more different colors on the edges, the faster the partitioning procedure works.
Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.