<p>I read your last comment in the Joshua's correct answer; if you need to transform EQ-GI to colored GI (i.e. you are in trouble with the colors assigned to the equivalence classes) you can use the following reduction:</p>

<p>Suppose that the starting graphs are $G_1 = (V_1, E_1)$, $G_2 = (V_2, E_2)$ and there are $q$ equivalence classes; then you can add to each graph a "permutator", i.e. a complete  graph on $|V_1|+1=|V_2|+1$ nodes ($K'_{|V_1|+1}$,$K''_{|V_2|+1}$) and use $q+1$ colors $c_1,...,c_q,c_{q+1}$.</p>

<p>In both $K'$ and $K''$,  $q$ nodes are distinguished and colored with $c_1,...,c_q$ the remaining nodes are colored with $c_{q+1}$.
The nodes of $G_1$ are colored with color $c_{q+1}$ and nodes in the same equivalence class are linked to the corresponding color in $K'$; the nodes of $G_2$ are colored with color $q+1$ and nodes in the same equivalence class are linked to the corresponding color in $K''$.</p>

<p>Also note that you can drop the colors and get an equivalent GI instance :-)</p>

<p><img src="https://i.sstatic.net/KGICW.png" alt="enter image description here">
<br>The reduction coresponding to the example in your comment</p>

CC BY-SA 3.0
2014-09-18T09:38:19.300Z
@user17410: ok, let me know if you need more clarifications
Marzio De Biasi
CC BY-SA 3.0
2014-09-17T18:17:45.093Z
This looks promising. I will check the correctness later on.
John D.
CC BY-SA 3.0
2014-09-17T09:50:47.567Z
2014-09-17T10:02:16.340Z
2014-09-17T10:02:16.340Z
Marzio De Biasi
<p>The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). Call the problem you describe EQ-GI. </p>

<p>GI is just the special case of EQ-GI where each graph has just one equivalence class consisting of all vertices.</p>

<p>In the other direction, to reduce EQ-GI to GI, let $(G, \sim_G)$ be a graph with equivalence relation with $n$ vertices, $m$ edges, and $c$ equivalence classes. Construct a graph $G'$ whose vertex set consists of the vertices of $G$, together with new vertices $v_1, \dotsc, v_c$, one for each equivalence class in $=_G$, as well as $n+c+1$ new vertices $w_0, \dotsc, w_{n+c}$. Connect the $w_i$'s in a path $w_0 - w_1 - w_2 - \dotsb - w_{n+c}$, connect each $v_i$ to $w_0$, and for every vertex in $G$, connect it to the corresponding equivalence class vertex $v_i$. Then $G'$ has at most $n + 2c + n +1 \leq O(n)$ vertices and can be constructed in essentially the same time bound. (It also has at most $m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$ edges - which is $O(m)$ for connected graphs - but that's somewhat less relevant since most GI algorithms have running times that essentially only depend on $n$.)</p>

<p><strong>Update</strong>: Since there was some confusion in the comments, I'm adding here a sketch of the correctness of the above argument. Given $(G_1, \sim_1)$ and $(G_2, \sim_2)$, let $G_1'$ and $G_2'$ be the graphs constructed as above; let $v_{i,1}$ denote the vertex $v_i$ from above in $G_1'$, and $v_{i,2}$ the one in $G_2'$, and similarly for $w_{i,1}$ and $w_{i,2}$. If there is an isomorphism $G_1' \cong G_2'$, it must send $w_{i,1}$ to $w_{i,2}$ for all $i$, since in each graph $w_{n+c}$ is the unique vertex that is the endpoint of any path of length at least $n+c+1$. In particular, $w_{0,1}$ maps to $w_{0,2}$. Since the neighbors of $w_0$ that aren't $w_1$ are exactly the $v_i$, the isomorphism must map the set $\{v_{1,1},\dotsc,v_{c,1}\}$ to the set $\{v_{1,2},\dotsc,v_{c,2}\}$ (and in particular both $\sim_1$ and $\sim_2$ must have the same number, $c$, of equivalence classes). Note that the isomorphism need not send $v_{i,1}$ to $v_{i,2}$ for all $i$, but is allowed to permute the indices of the $v$'s so long as the corresponding equivalence classes can be mapped to one another. Conversely, based on this description of how isomorphisms between $G_1'$ and $G_2'$ can look, it is easy to see that if $(G_1, \sim_1) \cong (G_2, \sim_2)$ then this gives an isomorphism $G_1' \cong G_2'$.</p>

CC BY-SA 3.0
2014-09-18T02:03:44.967Z
@user17410: I did not use any colors in my reduction - the resulting graphs $G'$ are uncolored (or, if you need it to be a reduction to Colored-GI, they are colored, but every vertex has the same color). I agree that the reduction you proposed in your second comment does not work, but that is not the reduction in my answer. I've edited the answer to sketch the proof of correctness.
Joshua Grochow
CC BY-SA 3.0
2014-09-18T19:14:15.557Z
Your correctness argument has convinced me. I jumped to conclusions to fast before taking the time to analyze your reduction, I apologize.
John D.
CC BY-SA 3.0
2014-09-17T06:24:34.220Z
As far as I understand there is a fundamental problem with your reduction. You basically enforce a unique invariant property on the set of vertices of every equivalence class. In this case you chose the eccentricity of a vertex as invariant property. For a graph $G$ let $f$ be a coloring. Let us say $=_f$ is the equivalence relation induced by $f$, i.e. $u =_f v$ iff $f(u) = f(v)$.
John D.
CC BY-SA 3.0
2014-09-17T06:24:49.437Z
Now, consider reducing EQ-GI to colored GI. By your argument for an input $(G,=_1),(H,=_2)$ it should suffice to pass $G,H$ and choose colorings $c_1,c_2$ which induce $=_1,=_2$. The problem here is that $(G,c) \cong (H,d)$ implies $(G,=_c) \cong (H,=_d)$ but the other direction is not necessarily true because we don't know the correspondence between the two sets of equivalence classes a priori.
John D.
CC BY-SA 3.0
2014-09-17T06:25:25.553Z
Stated differently, I fail to see how it would be possible for a mere graph transformation to reduce EQ-GI to colored GI at all because of the more complex constraints. It is clear however that your construction would work to reduce colored GI to GI.
John D.
CC BY-SA 3.0
2014-09-17T07:42:24.407Z
@user17410 EQ-GI *is* coloured GI. "Call the problem you describe EQ-GI." It's certainly possible for a graph transformation to reduce EQ-GI to GI: in fact this can be done for any isomorphism problem on relational structures to GI. Joshua's reduction looks correct to me; I had thought of a slightly simpler one that adds rather more vertices.
David Richerby
CC BY-SA 3.0
2014-09-17T08:20:48.400Z
@DavidRicherby EQ-GI and colored GI are not exactly the same. Consider the cycle graph on 4 vertices. Let $G$ be $1-2-3-4-1$ and $H$ be $1-3-2-4-1$. Let all vertices of both graphs be in single equivalence classes, i.e. both graphs have 4 equivalence classes.
John D.
CC BY-SA 3.0
2014-09-17T08:21:42.063Z
Now, the crucial point that hasn't been specified is how to choose which equivalence class gets which color (or $v_i$). The obvious way is to order the classes by size and then lexicographically according to their labels. In this case for both graphs $G,H$ in our example it holds that their color coincides with their label. Obviously, in EQ-GI these two graphs are isomorph whereas their colored versions aren't.
John D.
CC BY-SA 3.0
2014-09-17T04:27:14.190Z
2014-09-18T15:47:58.603Z
2014-09-18T15:47:58.603Z
Joshua Grochow
<p>A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that the coloring is obeyed, i.e. $c(v) = d(\pi(v))$ for all $v \in V(G)$.</p>

<p>This notion captures the isomorphism of colored graphs in a very strict sense. Consider the case where you have two political maps of the same region but they use different color sets. If one asks if they are colored in the same fashion one would assume this to mean whether there exists a bijective mapping between the two color sets such that the colors of both maps coincide via this mapping. This notion can be formalized by describing colored graphs as tuple $(G,\sim)$ where $\sim$ is an equivalence relation on the vertex set of $G$. We can then say two such graphs $(G,\sim_1)$ and $(H,\sim_2)$ are isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that for all pairs $v_1,v_2 \in V(G)$ it holds that 
$$v_1 \sim_1 v_2 \text{ iff } \pi(v_1) \sim_2 \pi(v_2)$$</p>

<p>My question is whether this concept has been studied previously w.r.t. finding canonical forms etc. and if so under what name it is known?</p>

CC BY-SA 3.0
2014-09-17T08:30:12.830Z
Please don't use the notation "$=$" for anything other than the equality relation!
David Richerby
<terminology><graph-isomorphism><equivalence>
Graph isomorphism with equivalence relation on the vertex set
John D.
# Graph isomorphism with equivalence relation on the vertex set

(Asked by: username_0 on 2014-09-16)

A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that the coloring is obeyed, i.e. $c(v) = d(\pi(v))$ for all $v \in V(G)$.

This notion captures the isomorphism of colored graphs in a very strict sense. Consider the case where you have two political maps of the same region but they use different color sets. If one asks if they are colored in the same fashion one would assume this to mean whether there exists a bijective mapping between the two color sets such that the colors of both maps coincide via this mapping. This notion can be formalized by describing colored graphs as tuple $(G,\sim)$ where $\sim$ is an equivalence relation on the vertex set of $G$. We can then say two such graphs $(G,\sim\_1)$ and $(H,\sim\_2)$ are isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that for all pairs $v\_1,v\_2 \in V(G)$ it holds that
$$v\_1 \sim\_1 v\_2 \text{ iff } \pi(v\_1) \sim\_2 \pi(v\_2)$$

My question is whether this concept has been studied previously w.r.t. finding canonical forms etc. and if so under what name it is known?

**Tags:** terminology, graph-isomorphism, equivalence
> **Comments:**
> **username_1**: Please don't use the notation "$=$" for anything other than the equality relation!  

---

## 2 answers

### Answer by username_3 on 2014-09-17. Score: 9 | Accepted answer

The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). Call the problem you describe EQ-GI.

GI is just the special case of EQ-GI where each graph has just one equivalence class consisting of all vertices.

In the other direction, to reduce EQ-GI to GI, let $(G, \sim\_G)$ be a graph with equivalence relation with $n$ vertices, $m$ edges, and $c$ equivalence classes. Construct a graph $G'$ whose vertex set consists of the vertices of $G$, together with new vertices $v\_1, \dotsc, v\_c$, one for each equivalence class in $=\_G$, as well as $n+c+1$ new vertices $w\_0, \dotsc, w\_{n+c}$. Connect the $w\_i$'s in a path $w\_0 - w\_1 - w\_2 - \dotsb - w\_{n+c}$, connect each $v\_i$ to $w\_0$, and for every vertex in $G$, connect it to the corresponding equivalence class vertex $v\_i$. Then $G'$ has at most $n + 2c + n +1 \leq O(n)$ vertices and can be constructed in essentially the same time bound. (It also has at most $m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$ edges - which is $O(m)$ for connected graphs - but that's somewhat less relevant since most GI algorithms have running times that essentially only depend on $n$.)

**Update**: Since there was some confusion in the comments, I'm adding here a sketch of the correctness of the above argument. Given $(G\_1, \sim\_1)$ and $(G\_2, \sim\_2)$, let $G\_1'$ and $G\_2'$ be the graphs constructed as above; let $v\_{i,1}$ denote the vertex $v\_i$ from above in $G\_1'$, and $v\_{i,2}$ the one in $G\_2'$, and similarly for $w\_{i,1}$ and $w\_{i,2}$. If there is an isomorphism $G\_1' \cong G\_2'$, it must send $w\_{i,1}$ to $w\_{i,2}$ for all $i$, since in each graph $w\_{n+c}$ is the unique vertex that is the endpoint of any path of length at least $n+c+1$. In particular, $w\_{0,1}$ maps to $w\_{0,2}$. Since the neighbors of $w\_0$ that aren't $w\_1$ are exactly the $v\_i$, the isomorphism must map the set $\{v\_{1,1},\dotsc,v\_{c,1}\}$ to the set $\{v\_{1,2},\dotsc,v\_{c,2}\}$ (and in particular both $\sim\_1$ and $\sim\_2$ must have the same number, $c$, of equivalence classes). Note that the isomorphism need not send $v\_{i,1}$ to $v\_{i,2}$ for all $i$, but is allowed to permute the indices of the $v$'s so long as the corresponding equivalence classes can be mapped to one another. Conversely, based on this description of how isomorphisms between $G\_1'$ and $G\_2'$ can look, it is easy to see that if $(G\_1, \sim\_1) \cong (G\_2, \sim\_2)$ then this gives an isomorphism $G\_1' \cong G\_2'$.

> **Comments:**
> **username_0**: As far as I understand there is a fundamental problem with your reduction. You basically enforce a unique invariant property on the set of vertices of every equivalence class. In this case you chose the eccentricity of a vertex as invariant property. For a graph $G$ let $f$ be a coloring. Let us say $=_f$ is the equivalence relation induced by $f$, i.e. $u =_f v$ iff $f(u) = f(v)$.  
> **username_0**: Now, consider reducing EQ-GI to colored GI. By your argument for an input $(G,=_1),(H,=_2)$ it should suffice to pass $G,H$ and choose colorings $c_1,c_2$ which induce $=_1,=_2$. The problem here is that $(G,c) \cong (H,d)$ implies $(G,=_c) \cong (H,=_d)$ but the other direction is not necessarily true because we don't know the correspondence between the two sets of equivalence classes a priori.  
> **username_0**: Stated differently, I fail to see how it would be possible for a mere graph transformation to reduce EQ-GI to colored GI at all because of the more complex constraints. It is clear however that your construction would work to reduce colored GI to GI.  
> **username_1**: @user17410 EQ-GI *is* coloured GI. "Call the problem you describe EQ-GI." It's certainly possible for a graph transformation to reduce EQ-GI to GI: in fact this can be done for any isomorphism problem on relational structures to GI. Joshua's reduction looks correct to me; I had thought of a slightly simpler one that adds rather more vertices.  
> **username_0**: @DavidRicherby EQ-GI and colored GI are not exactly the same. Consider the cycle graph on 4 vertices. Let $G$ be $1-2-3-4-1$ and $H$ be $1-3-2-4-1$. Let all vertices of both graphs be in single equivalence classes, i.e. both graphs have 4 equivalence classes.  
> **username_0**: Now, the crucial point that hasn't been specified is how to choose which equivalence class gets which color (or $v_i$). The obvious way is to order the classes by size and then lexicographically according to their labels. In this case for both graphs $G,H$ in our example it holds that their color coincides with their label. Obviously, in EQ-GI these two graphs are isomorph whereas their colored versions aren't.  
> **username_3**: @user17410: I did not use any colors in my reduction - the resulting graphs $G'$ are uncolored (or, if you need it to be a reduction to Colored-GI, they are colored, but every vertex has the same color). I agree that the reduction you proposed in your second comment does not work, but that is not the reduction in my answer. I've edited the answer to sketch the proof of correctness.  
> **username_0**: Your correctness argument has convinced me. I jumped to conclusions to fast before taking the time to analyze your reduction, I apologize.  

---

### Answer by username_2 on 2014-09-17. Score: 3

I read your last comment in the Joshua's correct answer; if you need to transform EQ-GI to colored GI (i.e. you are in trouble with the colors assigned to the equivalence classes) you can use the following reduction:

Suppose that the starting graphs are $G\_1 = (V\_1, E\_1)$, $G\_2 = (V\_2, E\_2)$ and there are $q$ equivalence classes; then you can add to each graph a "permutator", i.e. a complete graph on $|V\_1|+1=|V\_2|+1$ nodes ($K'\_{|V\_1|+1}$,$K''\_{|V\_2|+1}$) and use $q+1$ colors $c\_1,...,c\_q,c\_{q+1}$.

In both $K'$ and $K''$, $q$ nodes are distinguished and colored with $c\_1,...,c\_q$ the remaining nodes are colored with $c\_{q+1}$.
The nodes of $G\_1$ are colored with color $c\_{q+1}$ and nodes in the same equivalence class are linked to the corresponding color in $K'$; the nodes of $G\_2$ are colored with color $q+1$ and nodes in the same equivalence class are linked to the corresponding color in $K''$.

Also note that you can drop the colors and get an equivalent GI instance :-)

![enter image description here](https://i.sstatic.net/KGICW.png)
  
The reduction coresponding to the example in your comment

> **Comments:**
> **username_0**: This looks promising. I will check the correctness later on.  
> **username_2**: @user17410: ok, let me know if you need more clarifications  

---

