Determining whether two k-chromatic graphs are equivalent (not simply isomorphic) using IsomorphicGraphQ?

Question

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.

Answer 1

[Marking this "community". Anyone wanting to contribute code or comments should feel free to do so.]

You can modify @whuber's method for this. Say $r$ is the maximal vertex index. Call the colors $1,2,\ldots,n$, and each new vertex (one per color) $v_1,\ldots,v_n$. For $v_j$ add $r+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).

---

A variant of this approach uses just $r+1+n$ new vertices: $n$ to mark the colors and $r+1$ more to assure that none of the new vertices can possibly be equated with any of the original vertices.

The trick is to construct a graph $\Gamma_n$ having vertices of distinct degrees (ideally $0, 1, \ldots, n-1$, but any set of distinct degrees will do). Add in the universal graph $K_{r+1}$ on $r+1$ new vertices and connect every one of those new vertices to every vertex of $\Gamma_n$. In so doing, each of the $r+1$ new vertices will have degree $r + n \ge r+1$ and the vertices of $\Gamma_n$ will have degrees $r+1, r+2, \ldots, r+n$, all of which equal or exceed $r+1$. When the vertices of the original graph are connected to the vertices of $\Gamma_n$ to mark their colors, their degrees all increase by $1$, raising the maximal degree to just $r+1$, while at the same time the degree of each vertex of $\Gamma_n$ will increase by at least $1$, assuring their smallest degree is at least $r+2$. This keeps the $n+r+1$ additional vertices distinct from the original vertices of the graph (and from each other, too).

It remains only to create some version of $\Gamma_n$. The following is the smallest possible version in terms of numbers of edges added:

lGraph[v_List] /; Length@v > 1 :=  
  Module[{n = Length@v, x = Last@v, g, e},
   g = VertexAdd[lGraph@Most@v, x];
   e = Table[x \[UndirectedEdge] v[[i]], {i, 2, n, 2}];
   EdgeAdd[g, e]
   ];
lGraph[{x_}] := Graph[{x}, {}, GraphLayout -> "CircularEmbedding"];
lGraph[n_Integer] /; n >= 1 := lGraph[Unique@ConstantArray[x, n]]

It is constructed recursively. A new vertex x is adjoined to $\Gamma_{n-1}$ and connected to the vertices of highest degree in it (augmenting their degrees by $1$), until the degree of x differs from the degrees of all the other vertices. Here are examples of the first few:

GraphicsGrid[{lGraph[Range@#] & /@ Range[7]}, Frame -> All, FrameStyle -> GrayLevel[0.8]]

---

Incidentally, this seems to expose a bug (in MMA 8.0, at least): VertexDegree is incorrect. As an example, consider the penultimate graph in the figure, $\Gamma_6$:

lGraph[6] // VertexDegree

$ \{0, 8, 1, 7, 2, 6\}$

Quite clearly, though, the degrees in this graph are $\{0,5,1,4,2,3\}$ (reported in the order in which the vertices were added). According to the documentation, self-edges are counted twice, leading us to expect that VertexDegree would report values $\{0,6,1,5,2,4\}$--but it doesn't. Apparently, self-edges are counted as adding $4$ to the degree of each vertex rather than $2$!

To show that the display of the graph is not confusing the eye, we can inspect its internal structure:

EdgeList[lGraph[Range@6]]

$\{2- 2,3- 2,4- 2,4- 4,5- 2,5- 4,6- 2,6- 4,6- 6\}$

It is hard to imagine how any reasonable algorithm could report that vertex $2$ has degree $8$.