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

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?

• Does IsomorphicGraphQ handle weighted graphs? If so, assign to each color a distinct prime, and the weight of an edge the product of the vertex numbers. If not, you could expand the graph by making p vertices for every vertex assigned the prime p, and connecting each to every family of vertices coming from neighbors of the original. – Daniel Lichtblau Apr 6 '13 at 19:29
• igraph supports this functionality. I think there are two practical ways to access igraph from Mathematica: use RLink and call the R interface of igraph. This only works on Windows because RLink doesn't support external libraries on Mac/Linux. The other solution is using the igraph link by Mark McClure, check here please. This link does't yet expose the functions for coloured graph isomorphisms, so you'll need to write a bit of C code to get it working. It may take a couple of hours' work if you've never worked with igraph. – Szabolcs Apr 8 '13 at 4:40
• If you do choose to extend the igraph link to Mathematica with this, please do let me know (ideally, send me a pull request) – Szabolcs Apr 8 '13 at 4:42
• @Daniel Mathematica supports both edge and vertex weights, but IsomorphicGraphQ ignores them. – Szabolcs Apr 8 '13 at 4:45

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.

• I think this may be equivalent to what you do but stated somewhat differently. (1) For each color, add one new vertex (call these the "color" vertices). Connect it to every other vertex of that same color. (2) Connect each of these new vertices to one another. (3) If r is the maximal number of edges of any vertex in the original graph, and k the number of colors, then add (say) r-k further vertices and connect each only to the k newly added color vertices. (4) See if the new graphs are isomorphic. If so, recover an isomorphism of the original graphs. If not, they were not isomorphic. – Daniel Lichtblau Apr 8 '13 at 16:15
• (Almost forgot to upvote your answer. Also I agree your interpretation of the problem is the likely on, so mine was off target.) That said, I feel strangely compelled to add...if what I wrote in a prior comment is correct, then you managed to hide a really neat approach inside a serious jungle of notation. (But maybe what I wrote wasn't any improvement..) – Daniel Lichtblau Apr 8 '13 at 16:20
• @Daniel That's how I understand it too. Step (3) is meant to ensure that the colour-coding vertices won't be mapped to any true graph vertices when looking for isomorphisms. Another way to ensure this, when working with undirected graphs, would be to convert them to a directed graph. Each original edge would map to two directed edges (one in each direction), but the colour-coding vertices would be connected with only one, single-direction edge. – Szabolcs Apr 8 '13 at 16:43
• I'm wondering if step (3) is detrimental to efficiency. It seems it would introduce more symmetries (automorphisms) than necessary, and these would slow down IsomorphicGraphQ. – Szabolcs Apr 8 '13 at 16:45
• @Daniel I felt the notation was necessary to clarify the question. After introducing it, I gradually abandoned it whenever such detail was no longer needed. I believe your first comment is correct. – whuber Apr 8 '13 at 17:02

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

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:= IGraph["graph.isomorphic.vf2"][g, g, col1, col2]

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

In:= IGraph["graph.isomorphic.vf2"][g, g, col1, col3]
Out= 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}}]} *)
`