Symmetry Groups of Coloured Graphs

A perfect colouring of a simple undirected connected graph G is an edge colouring such that each vertex is incident with exactly one edge of each colour. This paper concerns the problem of representing groups by graphs with perfect colourings. We define groups of graph automorphisms that preserve the structure of the colouring and characterize these groups up to isomorphism. Our approach is based on the fact that every perfectly coloured graph is isomorphic to a Schreier coset graph on a group generated by involutions. The paper discusses the relationships identified in previous works regarding abstract groups as automorphism groups of graphs, offering insights into the understanding of symmetry groups associated with perfectly coloured graphs. Through the specification and investigation of these symmetry groups, the research contributes to the broader discourse on combinatorial maps and the conditions necessary for regularity within these mathematical structures.