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.
32
55
76
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.
Casali, Maria Rita; Gagliardi, Carlo
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/309530
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact