Determining whether two $k$-chromatic graphs are isomorphic (respecting vertex coloration)

Question

Consider the case where I have two $k$-chromatic graphs $G_1$ and $G_2$, i.e. two graphs where individual vertices can be colored with one of a set of $k$ total colors, and I would like to determine if the two graphs are equivalent while respecting vertex coloration. Is there a way to do this in Mathematica 8 or 9? If so, is there a known computational complexity for the algorithm being employed?

Answer 1

To avoid any misconstruction of this answer, let's begin with a clarification of the question. A $k$-coloring of a graph $\gamma$ is a map from its vertices $V(\gamma)$ into a set of cardinality $k$. Let's say that two $k$-colorings $f_1:\gamma\to K_1$ and $f_2:\gamma\to K_2$ of a given graph $\gamma$ are equivalent when there exists a bijection $g:K_1\to K_2$ for which $g\circ f_1 = f_2$: that is, $g$ merely renames the "colors."

Let $f_1:\gamma_1\to K_1$ and $f_2:\gamma_2\to K_2$ be two $k$-colored graphs. Any map $F$ from the vertices of $\gamma_1$ to the vertices of $\gamma_2$ creates a new $k$-coloring of $\gamma_1$ from the $k$-coloring of $\gamma_2$, called $F^*f_2$, via

$$F^*f_2(v) = f_2(F(v)).$$

This new coloring simply colors the vertices of $\gamma_1$ according to the colors of their images in $\gamma_2$.

The question seems to intend that two such $k$-colorings are "equivalent" when there exists a one-to-one correspondence between the vertices of these graphs, $F: V(\gamma_1)\to V(\gamma_2)$, which is at once a graph isomorphism and for which $F^*f_2$ is equivalent to $f_1$. In other words, there is an isomorphism of the graphs which creates the same coloring after a possible renaming of the colors: we do not demand that the colors be identical, vertex for vertex.

Analysis

The purpose of this answer is to point out that such an isomorphism can be found with algorithms that apply to uncolored graphs (enabling application of Mathematica's FindGraphIsomorphism command). It is based on the following construction. Suppose $f:\gamma\to K$ is a graph coloring and that the elements of $K$ are not among the vertices of $f$. For future use, take another set $K'$ which contains no vertices of $\gamma$ or elements of $K$. (Usually $K'$ will be empty.) Form the union of $\gamma$ and the universal graph on $K \cup K'$. To it adjoin all edges given by $f$: that is, whenever $v$ is a vertex of $\gamma$, make $(v, f(v))$ an edge in this union.

Call the result of this construction $\gamma \otimes_f(K\cup K')$. The point is this:

$f_1:\gamma_1\to K_1$ is equivalent to $f_2:\gamma_2\to K_2$ if and only if there exists a "suitable" $K'$ such that $\gamma_1\otimes_{f_1}(K_1\cup K')$ is isomorphic to $\gamma_2\otimes_{f_2}(K_2\cup K')$.

The implication (equivalence implies isomorphism) follows immediately from the definitions for any $K'$. Its inverse (isomorphism implies equivalence) follows from observing that we can always choose $K'$ sufficiently large to assure that the degrees of all the vertices coming from $K\cup K'$ in this graph differ from the degrees of any of the vertices coming from $\gamma_1$ or $\gamma_2$. Thus, any isomorphism must separately be an isomorphism of the universal graph on $K_1\cup K'$ with the universal graph on $K_2\cup K'$--which is merely a permutation of their vertices--and an isomorphism of $\gamma_1$ with $\gamma_2$. At the same time, any edge from $\gamma_1$ to $K_1$ gets mapped to an edge from $\gamma_2$ to $K_2$: this gives the desired equivalence of colorings. (Because the focus on this site is on the Mathematica solution, I leave the details to interested readers.)

Example

Consider these three graphs, $\gamma_1$, $\gamma_2,$ and $\gamma_3$:

All three are mutually isomorphic as graphs. It is visually evident that the first two colorings are not equivalent, because each pair of colors in the left graph $\gamma_1$ is diametrically opposite whereas that is not the case in the other two graphs. It is almost as clear that the last two graphs are equivalent: a counterclockwise rotation by $2\pi/3$ and a relabeling of the colors (green->blue, red->green, blue->red) will do it.

To address the question of the equivalence of their colorings, which can be construed as $k$-colorings for any $k\ge 3$, we form the augmented graphs $\gamma_i \otimes_{f_i}(K_i)$ (because $K'$ can be empty in this case) using GraphUnion and EdgeAdd:

In this figure, smaller vertices indicate those coming from the original graphs and the large vertices come from the $K_i$. Because each element of $K_i$ is a color, I have accordingly colored each large vertex to display its own color. Notice how this works: even had I left the smaller vertices not visibly colored, you could recover the original colorings just by noting which of the three large colored vertices each original vertex is connected to. This shows how any coloring can be encoded within an uncolored graph. (You can also partially distinguish the original vertices from the color vertices: the latter all have very high degrees, equal to $4$ in this case. In general, a color vertex $c$--that is, one coming from $K$--has a degree equal to $k + k' - 1$ plus the number of vertices of $\gamma$ having color $c$; $k'$ is the cardinality of $K'$.)

Specifically, these graphs can be recreated with the following vertices and edges:

v = {1, 2, 3, 4, 5, 6, blue, green, red};
e1 = {ue[1, 2], ue[2, 3], ue[3, 4], ue[4, 5], ue[5, 6], ue[6, 1], 
      ue[blue, green], ue[blue, red], ue[green, red], ue[1, red], 
      ue[2, green], ue[3, blue], ue[4, red], ue[5, green], ue[6, blue]};
e2 = {ue[1, 2], ue[2, 3], ue[3, 4], ue[4, 5], ue[5, 6], ue[6, 1], 
      ue[blue, green], ue[blue, red], ue[green, red], ue[1, red], 
      ue[2, green], ue[3, red], ue[4, blue], ue[5, green], ue[6, blue]};
e3 = {ue[1, 2], ue[2, 3], ue[3, 4], ue[4, 5], ue[5, 6], ue[6, 1], 
      ue[blue, green], ue[blue, red], ue[green, red], ue[1, red], 
      ue[2, green], ue[3, blue], ue[4, green], ue[5, red], ue[6, blue]};
g1 = Graph[v, e1 /. ue -> UndirectedEdge];
g2 = Graph[v, e2 /. ue -> UndirectedEdge];
g3 = Graph[v, e3 /. ue -> UndirectedEdge];

Now we merely inquire whether they are isomorphic as graphs:

FindGraphIsomorphism[g1,g2]

$\{\}$

As we already figured out, the first two graphs are not equivalent.

FindGraphIsomorphism[g3, g2]

$\{1\to 1,2\to 6,3\to 5,4\to 4,5\to 3,6\to 2,\text{blue}\to \text{green},\text{green}\to \text{blue},\text{red}\to \text{red}\}$

Notice how--as claimed--the isomorphism explicitly gives an isomorphism of the original vertices $\{1,2,3,4,5,6\}$ as well as a permutation of the colors. (This is not the same isomorphism I described originally: Mathematica found a different one.)

Evidently, creating these augmented graphs adds little computational burden when $k$ is small: the number of vertices is typically increased from $n$ to $n+k$ and the number of edges is increased by $n + (k+k')(k+k-1)/2$. Unless the graphs have some vertices of very high degree, $K'$ will be empty (so $k'=0$), indicating that the increase in the number of edges is relatively small. Only when $k$ is large compared to $n$ will this approach potentially become unwieldy.

I am reluctant to provide general-purpose code for this solution because the question does not specify how the coloring of the graph will be represented in Mathematica, but I hope the analysis makes it clear how to proceed.

Answer 2

You can use this package to call igraph through RLink. igraph can test the isomoprhism of coloured graphs (either edge or vertex colouring).

---

Note: igraph's interpretation of isomorphism with colouring is different from @whuber's above. It does not allow "renaming" of the colours.

Let's look at an example. With colour renaming (i.e. distinct but indistinguishable colours), the following graphs are isomorphic:

If we do not allow colour renaming, like igraph, then they are not. But the following two still are:

---

Let's build the same graphs that @whuber had:

g = CycleGraph[6]

col1 = {1, 2, 3, 1, 2, 3}
col2 = {2, 1, 3, 2, 1, 3}
col3 = {3, 2, 3, 1, 2, 1}

The three vectors col1, col2 and col3 represent the three colourings.

Now simply use

In[30]:= IGraph["graph.isomorphic.vf2"][g, g, col1, col2]

Out[30]= RObject[{{True}, {2., 1., 6., 5., 4., 3.}, {2., 1., 6., 5., 4., 3.}},
             RAttributes["names" :> {"iso", "map12", "map21"}]]

In[31]:= IGraph["graph.isomorphic.vf2"][g, g, col1, col3]    
Out[31]= RObject[{{False}, {}, {}}, 
 RAttributes["names" :> {"iso", "map12", "map21"}]]

On this cycle graph, the colourings col1 and col2 are isomorphic, but col1 and col3 are not.

Note that igraph will give one possible mapping as well, when it exists.

---

Alternatively, use the much better integrated IGraph/M package:

<<IGraphM`

With the VF2 algorithm:

IGVF2IsomorphicQ[{g, "VertexColors" -> col1}, {g, "VertexColors" -> col2}]
(* True *)

IGVF2IsomorphicQ[{g, "VertexColors" -> col1}, {g, "VertexColors" -> col3}]
(* False *)

With the Bliss algorithm:

IGBlissIsomorphicQ[{g, "VertexColors" -> col1}, {g, "VertexColors" -> col2}]
(* True *)

IGBlissIsomorphicQ[{g, "VertexColors" -> col1}, {g, "VertexColors" -> col3}]
(* False *)

We can also get the automorphism group of the coloured graphs as

PermutationGroup@IGBlissAutomorphismGroup[{g, "VertexColors" -> col1}]
(* PermutationGroup[{{4, 5, 6, 1, 2, 3}}] *)

GroupOrder[%]
(* 2 *)

GroupElements[%%]
(* {Cycles[{}], Cycles[{{1, 4}, {2, 5}, {3, 6}}]} *)