4
$\begingroup$

Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs have chromatic number equal to their clique number?

$\endgroup$

1 Answer 1

12
$\begingroup$

The book "Graph Homomorphisms" contains an elegant proof that a random graph admits only the identity endomorphism.

The term to search on is "rigid graph". (This has two different meanings but they are easy to distinguish.)

$\endgroup$
2
  • $\begingroup$ Is this the book? Graphs and Homomorphisms amazon.com/… $\endgroup$
    – CoffeeCat
    Commented Dec 14, 2014 at 17:58
  • $\begingroup$ Yes, that's it. I also think that if you google a bit you might find some notes online giving the proof. $\endgroup$ Commented Dec 14, 2014 at 23:02

You must log in to answer this question.