Re: [igraph] Graph isomorphism missed?

[Gábor Csárdi]

Well, that's not the definition we used for color isomorphism. What we
do is that in the mapping of the vertices, vertex 'v' can only be
mapped to vertex 'w' if they have the same color. My understanding is
that this is the "common" definition of isomorphism between colored
graphs, but I might be wrong.

Gabor

On Wed, Sep 12, 2012 at 9:22 AM, Louis Aslett <address@hidden> wrote:
> I might have misunderstood coloured graph isomorphisms, but from my
> understanding the following two graphs should be isomorphic (code in
> R).
>
> g1 <- graph.formula(1 -- 2:3, 2 -- 3, 3 -- 4)
> g2 <- graph.formula(1 -- 2, 2 -- 3, 2:3 -- 4)
> graph.count.isomorphisms.vf2(g1, g2, vertex.color1=c(1,2,2,1),
> vertex.color2=c(1,2,2,1))
>
> My understanding of coloured isomorphism is that two bijections are
> looked for f and g, say, such that f applied to one colour or vertex
> and g to the other results in equivalent adjacency to the original
> graph.  In this case, bijection f which switches 1 and 4, and another
> g which switches 2 and 3 does the job (I think).  However, the
> function says there are no isomorphisms.
>
> Any thoughts (or corrections to my understanding of coloured
> isomorphism) appreciated!
>
> Louis
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI