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.
r
is the maximal vertex index. Call the colors 1,...,k, and each new vertex (one per color) v_1,...,v_n. For v_j addr+j
new vertices; they will serve in a sense as anchors. Connect each ONLY to v_j. It is not hard to show that isomorphisms of the type you seek correspond to isomorphisms of these extended graphs, that is, vertices of a given color must map to vertices of that same color (because that color has a distinct number of these new 'anchor" vertices). $\endgroup$IsomorphicGraphQ
will either give True or False, depending of whether the graphs are isomorphic or not. It doesn't giveFalse
because it times out. But in v8 this function is buggy and may return incorrect results, so stick to v9. $\endgroup$