ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  15(1) (1995)   73-75
DOI: 10.7151/dmgt.1008


Steve Fisk

Bowdoin College
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


[Lov71] L. Lovász, On the cancellation law among finite relational structures, Periodica Math. Hung. 1 (1971) 145-156, doi: 10.1007/BF02029172.