<p><strong>Q2:</strong> a nice example is the graph labeling gadget used to prove that:</p>

<p><strong>Theorem</strong>: <em>Planar 3-connected colored GI $\leq_T^L$ planar 3-connected GI</em></p>

<p>See Thomas Thierauf, Fabian Wagner: <a href="http://link.springer.com/article/10.1007%2Fs00224-009-9188-4" rel="nofollow">The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace.</a> Theory Comput. Syst. 47(3): 655-673 (2010)</p>

<p>The "labeling gadget" used preserves the 3-connectedness and planarity constraints.</p>

CC BY-SA 3.0
2014-10-02T13:49:14.597Z
Thanks. What about the other questions?
joro
CC BY-SA 3.0
2014-10-02T14:59:37.520Z
@joro: I'll think about Q3,Q4; for Q1 I think that - perhaps - it is more interesting to ask "For which C polynomial GI *doesn't* imply (or it is unknown if it implies ...) polynomial (edge) colored GI?" (because for many graph classes  for which GI is polynomial time solvable, simple vertex/edge labelings don't put the graphs out of $\mathcal{C}$)
Marzio De Biasi
CC BY-SA 3.0
2014-10-02T15:09:17.017Z
Re Q1: if you find the question interesting ask it. Or perhaps edit this question with **Q1.1** attributed to yourself. Some thoughts while having beer :). (edge) colored graph trivially appears hypergraph to me. HGI is as easy as GI via reduction IIRC. Some cases of _restricted_ automorphisms are NP-complete and some are polynomial IIRC.
joro
CC BY-SA 3.0
2015-01-17T10:22:34.767Z
Added a paper in the question that might be relevant.
joro
CC BY-SA 3.0
2014-10-02T13:40:49.377Z
2014-10-02T13:40:49.377Z
Marzio De Biasi
<p>Partial answer, don't understand enough group theory, but two papers
appear to give partial results.</p>

<p>GI for circulants is polynomial.
Edged-colored GI for circulants is GI complete via
the simple reduction $G \to G'$.</p>

<p>Make a clique from $V(G)$ and color an edge $e \in E(G')$
with $1$ iff $e \in E(G)$ and $0$ otherwise.
To recover $G$ from $G'$ just take the edges colored $1$.</p>

<p>$G \cong H \iff G' \cong H'$ where the isomorphism preserves
the edge coloring.</p>

<p>$G'$ is edge colored clique and hence circulant.</p>

<p><a href="http://dept.math.lsa.umich.edu/undergrad/REU/ArchivedREUpapers/2010%20Papers/Odena%20paper.pdf" rel="nofollow">This paper</a> claims:</p>

<blockquote>
  <p>Abstract. We construct a deterministic algorithm that tests whether two
  circulant graphs are isomorphic. The running time is $ O(n^2 (\log n)^6 )$, where $n$ is the number of vertices of each graph. Our algorithm works for directed,
  undirected, and <strong>edge-colored circulants</strong>.</p>
</blockquote>

<p>The exact definition of "edge-colored" is not clear to me.</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.9010" rel="nofollow">Paper proving circulant GI is polynomial</a> in a footnote on p.1 claims:</p>

<blockquote>
  <p>By a graph we mean an ordinary graph, a digraph, or even an <strong>edge colored graph</strong></p>
</blockquote>

<p><a href="https://mathoverflow.net/questions/194189/when-is-edge-colored-circulant-isomorphism-polynomial">Asked on MO</a> what are the restrictions for the colorings.</p>

CC BY-SA 3.0
2015-01-18T11:35:22.490Z
2015-01-18T11:35:22.490Z
joro
<p>Crossposted from <a href="https://mathoverflow.net/questions/177927/when-polynomial-gi-implies-polynomial-edge-colored-gi">MO</a>.</p>

<p>(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).</p>

<p>There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge colored GI the simplest
is to replace colored edge by a GI preserving gadget encoding
the color (subdividing edge enough times is the simplest case).
For vertex colored GI, attach some gadget to a vertex.</p>

<p>Suppose GI is polynomial for some graph class $C$.</p>

<blockquote>
  <p>Q1 For which $C$ polynomial GI implies polynomial
  (edge) colored GI?</p>
</blockquote>

<p>Using a reduction with gadgets might make the graphs
not members of $C$.</p>

<p>On the other hand certain gadgets/transformations
might make the graphs members of some other polynomial
GI class.</p>

<p>Example of edge colored reduction $ G \to G'$.</p>

<p>Make a clique of $V(G)$. Color edges in $E(G)$ with $1$
and non-edges with $0$.  It is the coloring function
that preserves $G$ and to recover $G$ from $G'$ just
take the edges colored $1$. $G'$ is clique, cograph,
permutation graph and almost sure in many other nice
classes. Subdividing the edges odd number of times
(distinct for $0,1$ removes the colors and makes $G'$
perfect bipartite graph, preserving isomorphism).</p>

<p>Maybe another approach is to take the line graph
of $G'$ and add pendant (universal) vertices connected
to vertices corresponding to $E(G')$.</p>

<blockquote>
  <p>Q2 Are there nice gadgets/transformations for similar
  constructions?</p>
</blockquote>

<p>Thought about planarizing $G'$ by choosing some
universal drawing of the clique and replacing
edge crossing by planar gadgets preserving colors
say $C_4,C_6$ for equal colors and something else
for distinct colors. Don't know if this preserves
isomorphism.</p>

<p>Another possible approach might be automorphism
preserving coloring or subdivide every edge of
$K_n$, use 3 colors ${0,1,2}$ for vertices $V(G),E(G),E(\overline{G})$
and try to recognize self complementary graphs by
automorphism exchanging $E(G)$ and $E(\overline{G})$.</p>

<blockquote>
  <p>Q3 Is the automorphism group of the subdivision of $K_n$
  tractable to compute?</p>
</blockquote>

<p>The orders after the few initial terms are $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$
which is <a href="https://oeis.org/A052565">A052565</a></p>

<p>Dima suggests this might be easy for $n$ large enough and the initial
terms are exceptions.</p>

<blockquote>
  <p>Q4 Given vertex colored subdivision of $K_n$ for $n &gt; 4$ and its automorphism group
  where the high degree vertices are colored $0$, some degree $2$
  are $1$ and the other are $2$, what is the complexity to find
  automorphism exchanging $1$ and $2$?</p>
</blockquote>

<p><strong>Added</strong> The paper <a href="http://nozdr.ru.sci-hub.org/data/media/biblioteka/kolxo3/Cs_Computer_science/CsLn_Lecture%20notes/Algorithms%20-%20ESA%202000,%208%20conf.(LNCS1879,%20Springer,%202000)(ISBN%20354041004X)(462s).pdf#page=86">On Recognizing Cayley Graphs p 86</a> claims:</p>

<blockquote>
  <p>Given a class C of Cayley graphs, and given an edge-colored
  graph G of n vertices and m edges, we are interested in the problem of
  checking whether there exists an isomorphism φ preserving the colors
  such that G is isomorphic by φ to a graph in C colored by the elements
  of its generating set. In this paper, we give an O(m log n)-time algorithm
  to check whether G is color-isomorphic to a Cayley graph.</p>
</blockquote>

<p>This appears close to the question, is it relevant?</p>

CC BY-SA 3.0
2015-01-19T13:55:24.573Z
There is relation with hypergraphs. Colored edge (u,v,c) might be treated as hyperedge and there is reduction hypergraph to graph.
joro
<graph-theory><graph-isomorphism><automorphism>
When polynomial GI implies polynomial (edge) colored GI?
joro
# When polynomial GI implies polynomial (edge) colored GI?

(Asked by: username_0 on 2014-10-02)

Crossposted from [MO](https://mathoverflow.net/questions/177927/when-polynomial-gi-implies-polynomial-edge-colored-gi).

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).

There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge colored GI the simplest
is to replace colored edge by a GI preserving gadget encoding
the color (subdividing edge enough times is the simplest case).
For vertex colored GI, attach some gadget to a vertex.

Suppose GI is polynomial for some graph class $C$.

> Q1 For which $C$ polynomial GI implies polynomial
> (edge) colored GI?

Using a reduction with gadgets might make the graphs
not members of $C$.

On the other hand certain gadgets/transformations
might make the graphs members of some other polynomial
GI class.

Example of edge colored reduction $ G \to G'$.

Make a clique of $V(G)$. Color edges in $E(G)$ with $1$
and non-edges with $0$. It is the coloring function
that preserves $G$ and to recover $G$ from $G'$ just
take the edges colored $1$. $G'$ is clique, cograph,
permutation graph and almost sure in many other nice
classes. Subdividing the edges odd number of times
(distinct for $0,1$ removes the colors and makes $G'$
perfect bipartite graph, preserving isomorphism).

Maybe another approach is to take the line graph
of $G'$ and add pendant (universal) vertices connected
to vertices corresponding to $E(G')$.

> Q2 Are there nice gadgets/transformations for similar
> constructions?

Thought about planarizing $G'$ by choosing some
universal drawing of the clique and replacing
edge crossing by planar gadgets preserving colors
say $C\_4,C\_6$ for equal colors and something else
for distinct colors. Don't know if this preserves
isomorphism.

Another possible approach might be automorphism
preserving coloring or subdivide every edge of
$K\_n$, use 3 colors ${0,1,2}$ for vertices $V(G),E(G),E(\overline{G})$
and try to recognize self complementary graphs by
automorphism exchanging $E(G)$ and $E(\overline{G})$.

> Q3 Is the automorphism group of the subdivision of $K\_n$
> tractable to compute?

The orders after the few initial terms are $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$
which is [A052565](https://oeis.org/A052565)

Dima suggests this might be easy for $n$ large enough and the initial
terms are exceptions.

> Q4 Given vertex colored subdivision of $K\_n$ for $n > 4$ and its automorphism group
> where the high degree vertices are colored $0$, some degree $2$
> are $1$ and the other are $2$, what is the complexity to find
> automorphism exchanging $1$ and $2$?

**Added** The paper [On Recognizing Cayley Graphs p 86](http://nozdr.ru.sci-hub.org/data/media/biblioteka/kolxo3/Cs_Computer_science/CsLn_Lecture%20notes/Algorithms%20-%20ESA%202000,%208%20conf.(LNCS1879,%20Springer,%202000)(ISBN%20354041004X)(462s).pdf#page=86) claims:

> Given a class C of Cayley graphs, and given an edge-colored
> graph G of n vertices and m edges, we are interested in the problem of
> checking whether there exists an isomorphism φ preserving the colors
> such that G is isomorphic by φ to a graph in C colored by the elements
> of its generating set. In this paper, we give an O(m log n)-time algorithm
> to check whether G is color-isomorphic to a Cayley graph.

This appears close to the question, is it relevant?

**Tags:** graph-theory, graph-isomorphism, automorphism
> **Comments:**
> **username_0**: There is relation with hypergraphs. Colored edge (u,v,c) might be treated as hyperedge and there is reduction hypergraph to graph.  

---

## 2 answers

### Answer by username_1 on 2014-10-02. Score: 4

**Q2:** a nice example is the graph labeling gadget used to prove that:

**Theorem**: *Planar 3-connected colored GI $\leq\_T^L$ planar 3-connected GI*

See Thomas Thierauf, Fabian Wagner: [The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace.](http://link.springer.com/article/10.1007%2Fs00224-009-9188-4) Theory Comput. Syst. 47(3): 655-673 (2010)

The "labeling gadget" used preserves the 3-connectedness and planarity constraints.

> **Comments:**
> **username_0**: Thanks. What about the other questions?  
> **username_1**: @joro: I'll think about Q3,Q4; for Q1 I think that - perhaps - it is more interesting to ask "For which C polynomial GI *doesn't* imply (or it is unknown if it implies ...) polynomial (edge) colored GI?" (because for many graph classes  for which GI is polynomial time solvable, simple vertex/edge labelings don't put the graphs out of $\mathcal{C}$)  
> **username_0**: Re Q1: if you find the question interesting ask it. Or perhaps edit this question with **Q1.1** attributed to yourself. Some thoughts while having beer :). (edge) colored graph trivially appears hypergraph to me. HGI is as easy as GI via reduction IIRC. Some cases of _restricted_ automorphisms are NP-complete and some are polynomial IIRC.  
> **username_0**: Added a paper in the question that might be relevant.  

---

### Answer by username_0 on 2015-01-18. Score: 1

Partial answer, don't understand enough group theory, but two papers
appear to give partial results.

GI for circulants is polynomial.
Edged-colored GI for circulants is GI complete via
the simple reduction $G \to G'$.

Make a clique from $V(G)$ and color an edge $e \in E(G')$
with $1$ iff $e \in E(G)$ and $0$ otherwise.
To recover $G$ from $G'$ just take the edges colored $1$.

$G \cong H \iff G' \cong H'$ where the isomorphism preserves
the edge coloring.

$G'$ is edge colored clique and hence circulant.

[This paper](http://dept.math.lsa.umich.edu/undergrad/REU/ArchivedREUpapers/2010%20Papers/Odena%20paper.pdf) claims:

> Abstract. We construct a deterministic algorithm that tests whether two
> circulant graphs are isomorphic. The running time is $ O(n^2 (\log n)^6 )$, where $n$ is the number of vertices of each graph. Our algorithm works for directed,
> undirected, and **edge-colored circulants**.

The exact definition of "edge-colored" is not clear to me.

[Paper proving circulant GI is polynomial](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.9010) in a footnote on p.1 claims:

> By a graph we mean an ordinary graph, a digraph, or even an **edge colored graph**

[Asked on MO](https://mathoverflow.net/questions/194189/when-is-edge-colored-circulant-isomorphism-polynomial) what are the restrictions for the colorings.


---

