2
$\begingroup$

(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

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 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?

$\endgroup$
  • $\begingroup$ How is A052565 relevant here? What are these numbers counting? $\endgroup$ – Dima Pasechnik Aug 6 '14 at 13:28
  • $\begingroup$ @DimaPasechnik The numbers are the orders of the automorphism groups of subdivision of K_n and they showed up in OEIS (modulo errors). $\endgroup$ – joro Aug 6 '14 at 13:38
  • $\begingroup$ Do you mean a particular subdivision of $K_n$? (I have trouble reading English with missing articles). In your description, you seem to have defined a family of subdivisions for a given $n$, not just one particular. $\endgroup$ – Dima Pasechnik Aug 6 '14 at 14:24
  • $\begingroup$ @DimaPasechnik I believe this is the usual meaning of subdivision: by subdivision I mean subdivide every edge once: (u,v) becomes (u,(u,v))((u,v),v). $\endgroup$ – joro Aug 6 '14 at 14:30
  • 1
    $\begingroup$ OK; then please write "the subdivision", not just "subdivision". Anyhow, I am sure that the automorphism group of such a graph is easy to describe for any $n$. (not sure though what you mean by "tractable to compute" - by some particular algorithm? Or do you mean "describe"?) $\endgroup$ – Dima Pasechnik Aug 6 '14 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.