ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 15(1) (1995)
Brunswick, Me 04011, U.S.A.
A homomorphism from one graph to another is a map that sends vertices to vertices and
edges to edges. We denote the number of homomorphisms from G to H by
|G→H|. If F is
a collection of graphs, we say that F distinguishes
graphs G and H if there is some member X of F
such that |G→X |≠|H→X|. F
is a distinguishing family if it distinguishes all pairs of graphs.
We show that various collections of graphs are a distinguishing family.
Keywords: graph homomorphism, chromatic number
1991 Mathematics Subject Classification: 05C15