igraph-help
[Top][All Lists]

## Re: [igraph] Graph isomorphism missed?

 From: Louis Aslett Subject: Re: [igraph] Graph isomorphism missed? Date: Wed, 12 Sep 2012 15:53:09 +0100

```Thanks, yes that's what I meant in my rather imperfect rambling
definition!  In the example I sent in the first mail, nodes 1 and 4
are colour 1; nodes 2 and 3 are colour 2.  My understanding is that
simply switching labels within colours is an isomorphism?

Thanks,

Louis

On 12 September 2012 14:49, Gábor Csárdi <address@hidden> wrote:
> 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
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> --
> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>
> _______________________________________________
> igraph-help mailing list
> https://lists.nongnu.org/mailman/listinfo/igraph-help

```