A code for m-bipartite edge-coloured graphs

An (n+1)-coloured graph $(\Gamma,\gamma)$ is said to be m-bipartite if m is the maximum integer so that every m-residue of $(\Gamma,\gamma)$ (i.e. every connected subgraph whose edges are coloured by only m colours) is bipartite; obviously, every (n+1)-coloured graph, with $n \ge 2$, results to be m-bipartite for some m, with $\ 2 \le m \le n+1$. In this paper, a numerical code of length $(2n-m+1) \times q$ is assigned to each m-bipartite (n+1)-coloured graph of order 2q.Then, it is proved that any two such graphs have the same code if and only if they are colour-isomorphic, i.e. if a graph isomorphism exists, which transforms the graphs one into the other, up to permutation of the edge-colouring. More precisely, if H is a given group of permutations on the colour set, we face the problem of algorithmically recognizing H-isomorphic coloured graphs by means of a suitable definition of H-code.