lhsoicher
commented
3 years ago In GRAPE, a graph with colour-classes is a record having (at least) the components graph (which should be a graph in GRAPE format), and colourClasses (which should be a list of (pairwise-disjoint non-empty) sets partitioning the vertex-set of the graph).
In particular, a graph with colour-classes is not made by adding the component colour-classes to a GRAPE graph, as you have done.
An isomorphism from one graph with colour-classes to a second is a graph isomorphism from the first graph to the second which additionally maps the first list of colour-classes to the second (classwise). In other words, the ordering of the colour classes is "fixed".
For example:
gap> gamma := JohnsonGraph(5,3); rec( adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]), isGraph := true, isSimple := true, names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ] ) gap> delta := JohnsonGraph(5,2); rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> IsIsomorphicGraph( gamma, delta ); true gap> IsIsomorphicGraph(
rec(graph:=gamma, colourClasses:=[[7],[1,2,3,4,5,6,8,9,10]]), rec(graph:=delta, colourClasses:=[[10],[1..9]]) );true gap> IsIsomorphicGraph( rec(graph:=gamma, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]), rec(graph:=delta, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]) ); false
Please see Chapter 8 in the GRAPE manual.
From: markusbaumeister @.***> Sent: 21 September 2021 14:27 To: gap-packages/grape Cc: Subscribed Subject: [gap-packages/grape] Coloured isomorphism check should allow colour order to be fixed (#30)
A graph colouring is given by an ordered list of colour classes. In the current implementation of graph isomorphism, the ordering is not preserved. However, there are applications in which the ordering has to be preserved, for example if we describe isomorphism of incidence structures as graph isomorphism. It would be nice if both possibilities were covered by grape.
Here is an example of the incidence graphs of cube and octahedron: cube_graph := rec( adjacencies := [ [ 9, 12, 16 ], [ 9, 10, 13 ], [ 10, 11, 14 ], [ 11, 12, 15 ], [ 16, 19, 20 ], [ 13, 17, 20 ], [ 14, 17, 18 ], [ 15, 18, 19 ], [ 1, 2, 21, 22 ], [ 2, 3, 21, 23 ], [ 3, 4, 21, 25 ], [ 1, 4, 21, 24 ], [ 2, 6, 22, 23 ], [ 3, 7, 23, 25 ], [ 4, 8, 24, 25 ], [ 1, 5, 22, 24 ], [ 6, 7, 23, 26 ], [ 7, 8, 25, 26 ], [ 5, 8, 24, 26 ], [ 5, 6, 22, 26 ], [ 9, 10, 11, 12 ], [ 9, 13, 16, 20 ], [ 10, 13, 14, 17 ], [ 12, 15, 16, 19 ], [ 11, 14, 15, 18 ], [ 17, 18, 19, 20 ] ], colourClasses := [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], [ 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ], [ 21, 22, 23, 24, 25, 26 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], order := 26, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26 ] ) oct_graph := rec( adjacencies := [ [ 7, 8, 9, 10 ], [ 7, 11, 12, 13 ], [ 8, 11, 14, 15 ], [ 9, 14, 16, 17 ], [ 10, 12, 16, 18 ], [ 13, 15, 17, 18 ], [ 1, 2, 19, 21 ], [ 1, 3, 19, 25 ], [ 1, 4, 23, 25 ], [ 1, 5, 21, 23 ], [ 2, 3, 19, 22 ], [ 2, 5, 20, 21 ], [ 2, 6, 20, 22 ], [ 3, 4, 24, 25 ], [ 3, 6, 22, 24 ], [ 4, 5, 23, 26 ], [ 4, 6, 24, 26 ], [ 5, 6, 20, 26 ], [ 7, 8, 11 ], [ 12, 13, 18 ], [ 7, 10, 12 ], [ 11, 13, 15 ], [ 9, 10, 16 ], [ 14, 15, 17 ], [ 8, 9, 14 ], [ 16, 17, 18 ] ], colourClasses := [ [ 1, 2, 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ], [ 19, 20, 21, 22, 23, 24, 25, 26 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], order := 26, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26 ] ) These are currently found to be isomorphic since they are dual to each other. gap> IsIsomorphicGraph(cube_graph, oct_graph); true
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/gap-packages/grape/issues/30, or unsubscribehttps://github.com/notifications/unsubscribe-auth/ABXNAOGP3QUE6RNWOPPT2WTUDCB2TANCNFSM5EOOJEKQ. Triage notifications on the go with GitHub Mobile for iOShttps://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Androidhttps://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
markusbaumeister
A graph colouring is given by an ordered list of colour classes. In the current implementation of graph isomorphism, the ordering is not preserved. However, there are applications in which the ordering has to be preserved, for example if we describe isomorphism of incidence structures as graph isomorphism. It would be nice if both possibilities were covered by grape.
Here is an example of the incidence graphs of cube and octahedron:
cube_graph := rec( adjacencies := [ [ 9, 12, 16 ], [ 9, 10, 13 ], [ 10, 11, 14 ], [ 11, 12, 15 ], [ 16, 19, 20 ], [ 13, 17, 20 ], [ 14, 17, 18 ], [ 15, 18, 19 ], [ 1, 2, 21, 22 ], [ 2, 3, 21, 23 ], [ 3, 4, 21, 25 ], [ 1, 4, 21, 24 ], [ 2, 6, 22, 23 ], [ 3, 7, 23, 25 ], [ 4, 8, 24, 25 ], [ 1, 5, 22, 24 ], [ 6, 7, 23, 26 ], [ 7, 8, 25, 26 ], [ 5, 8, 24, 26 ], [ 5, 6, 22, 26 ], [ 9, 10, 11, 12 ], [ 9, 13, 16, 20 ], [ 10, 13, 14, 17 ], [ 12, 15, 16, 19 ], [ 11, 14, 15, 18 ], [ 17, 18, 19, 20 ] ], colourClasses := [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], [ 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ], [ 21, 22, 23, 24, 25, 26 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], order := 26, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26 ] )oct_graph := rec( adjacencies := [ [ 7, 8, 9, 10 ], [ 7, 11, 12, 13 ], [ 8, 11, 14, 15 ], [ 9, 14, 16, 17 ], [ 10, 12, 16, 18 ], [ 13, 15, 17, 18 ], [ 1, 2, 19, 21 ], [ 1, 3, 19, 25 ], [ 1, 4, 23, 25 ], [ 1, 5, 21, 23 ], [ 2, 3, 19, 22 ], [ 2, 5, 20, 21 ], [ 2, 6, 20, 22 ], [ 3, 4, 24, 25 ], [ 3, 6, 22, 24 ], [ 4, 5, 23, 26 ], [ 4, 6, 24, 26 ], [ 5, 6, 20, 26 ], [ 7, 8, 11 ], [ 12, 13, 18 ], [ 7, 10, 12 ], [ 11, 13, 15 ], [ 9, 10, 16 ], [ 14, 15, 17 ], [ 8, 9, 14 ], [ 16, 17, 18 ] ], colourClasses := [ [ 1, 2, 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ], [ 19, 20, 21, 22, 23, 24, 25, 26 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], order := 26, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26 ] )These are currently found to be isomorphic since they are dual to each other.gap> IsIsomorphicGraph(cube_graph, oct_graph); true