In a previous question of mine, I asked whether Mathematica's built-in routines could determine an isomorphism for two $k$-chromatic graphs, Determining whether two $k$-chromatic graphs are isomorphic (respecting vertex coloration). In response, the user whuber came up with a really neat/clever technique to add a (complete graph) module to the original $k$-chromatic graphs under comparison s.t. an isomorphism exists for the two $k$-chromatic graphs iff an isomorphism exists for their monochromatic forms with the attached module. This, as whubar points out, allows one to proceed using Mathematica's built-in functions IsomorphicGraphQ or FindGraphIsomorphism.
Here I'd like to ask a slightly different question -
Let $G_1$ and $G_2$ be two $k$-chromatic graphs, i.e. graphs where vertices can be independently assigned one of up to $k$ unique colors (I am open to any method of implementation for this in Mathematica 8 or 9). I'd like to know if $G_1$ and $G_2$ are equivalent rather than simply isomorphic. In other words, I'd like to know if an isomorphism exists for the monochromatic versions of $G_1$ and $G_2$ s.t. the same isomorphism applied to their $k$-chromatic forms works without color reassignment.
Is it possible to replace each colored vertex with a monochromatic "widget" s.t. a positive result for IsomorphicGraphQ or FindGraphIsomorphism will imply the equivalence of the $k$-chromatic forms of $G_1$ and $G_2$?
Also, is an answer of "False" from IsomorphicGraphQ (or the return of an empty set for FindGraphIsomorphism) necessarily indicative of their being no isomorphism? Or do these algorithms simply time out if the number of graph components are too large? It would be extremely helpful to know if the latter is true since this would require me to write my own implementation.