<p>In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same arguments works for edge colors as well. For example, you could subdivide each edge and instert a new vertex that encodes the edge color.</p>

CC BY-SA 4.0
2019-12-24T16:30:21.027Z
Definitely, this reduction implies a polynomial time algorithm, which is worth knowing, thanks! Now, looking at Proposition 4.5 (and 4.2, which it extends), the arguments are group-theoretic. If I understand well, having at most $d$ neighbors of the same color essentially implies that the factors of the composition series of $Aut(G)$ are subgroups of $S_d$, which is enough to know. In contrast, the arguments in my question are almost direct (and the setting natural), so I'll keep the question open a bit longer to see if anyone has seen these particular arguments (and eventually accept if not).
Arnaud Casteigts
CC BY-SA 4.0
2019-12-19T18:07:27.703Z
2019-12-19T18:07:27.703Z
user55611
<p>An edge-colored graph <span class="math-container">$G$</span> is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is <em>proper</em> if all adjacent edges in <span class="math-container">$G$</span> have different colors. I recently realized that isomorphism between two such graphs can be tested in polynomial time. The arguments are pretty simple and the question natural, so this fact should already be mentioned somewhere. However, I could not find it so far.</p>

<p>The arguments: Fix an arbitrary vertex <span class="math-container">$v_1$</span> in <span class="math-container">$G_1$</span>. We will try to send it to every vertex <span class="math-container">$v_2$</span> of <span class="math-container">$G_2$</span> successively, until either a valid bijection is found (accept) or all the vertices of <span class="math-container">$G_2$</span> have been tried (reject). The key point is that once the selection of <span class="math-container">$v_2$</span> is made, no other choice remains to be done, because local constraints imposed by the colors recursively determine the remaining of the bijection. For instance, if <span class="math-container">$v_1$</span> shares an edge colored <span class="math-container">$c$</span> with vertex <span class="math-container">$u_1$</span>, then this vertex <em>must</em> be sent to a vertex that shares an edge colored <span class="math-container">$c$</span> with <span class="math-container">$v_2$</span>. This vertex (if any qualifies) must be unique due to the fact that the coloring is proper.</p>

<p>Has anyone seen such an observation somewhere or has an idea where to find it?</p>

CC BY-SA 4.0
2019-12-19T05:08:23.327Z
This argument is very close to the one showing that the exact version of unique label cover is solvable in polynomial time.
Yonatan N
CC BY-SA 4.0
2019-12-29T14:35:23.823Z
Suggest you edit the post to clarify that by "isomorphism between two such graphs" you mean one that preserves the edge colors (which is not the standard definition of an isomorphism between graphs).
Neal Young
<reference-request><graph-isomorphism><graph-colouring>
Complexity of graph isomorphism with properly colored edges (ref. request)
Arnaud Casteigts
# Complexity of graph isomorphism with properly colored edges (ref. request)

(Asked by: username_0 on 2019-12-18)

An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is *proper* if all adjacent edges in $G$ have different colors. I recently realized that isomorphism between two such graphs can be tested in polynomial time. The arguments are pretty simple and the question natural, so this fact should already be mentioned somewhere. However, I could not find it so far.

The arguments: Fix an arbitrary vertex $v\_1$ in $G\_1$. We will try to send it to every vertex $v\_2$ of $G\_2$ successively, until either a valid bijection is found (accept) or all the vertices of $G\_2$ have been tried (reject). The key point is that once the selection of $v\_2$ is made, no other choice remains to be done, because local constraints imposed by the colors recursively determine the remaining of the bijection. For instance, if $v\_1$ shares an edge colored $c$ with vertex $u\_1$, then this vertex *must* be sent to a vertex that shares an edge colored $c$ with $v\_2$. This vertex (if any qualifies) must be unique due to the fact that the coloring is proper.

Has anyone seen such an observation somewhere or has an idea where to find it?

**Tags:** reference-request, graph-isomorphism, graph-colouring
> **Comments:**
> **username_1**: This argument is very close to the one showing that the exact version of unique label cover is solvable in polynomial time.  
> **username_2**: Suggest you edit the post to clarify that by "isomorphism between two such graphs" you mean one that preserves the edge colors (which is not the standard definition of an isomorphism between graphs).  

---

## 1 answers

### Answer by username_3 on 2019-12-19. Score: 5

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same arguments works for edge colors as well. For example, you could subdivide each edge and instert a new vertex that encodes the edge color.

> **Comments:**
> **username_0**: Definitely, this reduction implies a polynomial time algorithm, which is worth knowing, thanks! Now, looking at Proposition 4.5 (and 4.2, which it extends), the arguments are group-theoretic. If I understand well, having at most $d$ neighbors of the same color essentially implies that the factors of the composition series of $Aut(G)$ are subgroups of $S_d$, which is enough to know. In contrast, the arguments in my question are almost direct (and the setting natural), so I'll keep the question open a bit longer to see if anyone has seen these particular arguments (and eventually accept if not).  

---

