
- This event has passed.
Atlantic Graph Theory Seminar
January 29, 2025 @ 3:30 pm - 4:30 pm
An m-edge-coloured graph consists of a set of vertices, any two of which are either joined by an edge of one of m colours or not joined at all. The operation of switching at a vertex v of an m-edge-coloured graph with respect to an element of a subgroup \Gamma of S_m permutes the colours of the edges incident with v. Switching defines an equivalence relation on the set of all m-edge-coloured graphs; G and H are \Gamma-switch-equivalent if there exists a sequence of switches that transform G into H.
We consider the following problems and their solutions. For a fixed subgroup \Gamma of S_m:
1) determine the number of equivalence classes of k-vertex m-edge-coloured graphs under switching with respect to \Gamma.
2) how hard is it to determine whether given m-edge-coloured graphs G and H are \Gamma-switch equivalent?
3) for a fixed m-edge-coloured graph H, how hard is it to determine whether a given m-edge-coloured graph G can be switched with respect to \Gamma so that there is a homomorphism of the transformed m-edge-coloured graph to H? (A homomorphism is a mapping of V(G) to V(H) that preserves edges and colours.)
We will also discuss extending these results to (m,n)-mixed graphs. These have m different colours of edges and n different colours of arcs.