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.
A code for m-bipartite edge-coloured graphs / Casali, Maria Rita; Gagliardi, Carlo. - In: RENDICONTI DELL'ISTITUTO DI MATEMATICA DELL'UNIVERSITÀ DI TRIESTE. - ISSN 0049-4704. - STAMPA. - 32:(2001), pp. 55-76.
A code for m-bipartite edge-coloured graphs
CASALI, Maria Rita;GAGLIARDI, Carlo
2001
Abstract
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.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris