Critical graphs and endomorphisms We call a finite simple undirected graph $G=(V,E)$ critical if $\chi(G\setminus\{v\}) < \chi(G)$ for all $v\in V$.
If $G$ is critical then for any graph homomorphism $f:G\to G$ we have that $f$ is surjective, and therefore bijective. (The reason is that whenever $f: G\to H$ is a graph homomorphism, then $\chi(G)\leq \chi(H)$.)
What is an example of a graph $G$ that is not critical, but every graph homomorphism $f:G\to G$ is surjective?
 A: There are lots of examples. They even have a name for when a graph has only surjective endomorphisms, such a graph is called a core. In fact every graph is homomorphically equivalent (has a homomorphism both to and from) a unique core. A good reference for cores is Godsil and Royle's Algebraic Graph Theory. Also, Hahn and Tardif's survey on graph homomorphisms is a good reference and it is available online: http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf
More specifically, you could consider the Kneser graphs, which includes the Petersen graph.
Also, I recently proved that all strongly regular graphs are pseudocores: every endomorphism is either surjective or is a mapping to a max clique (http://arxiv.org/abs/1601.00969). From here it follows that these graphs are cores unless they have clique number equal to chromatic number (in which case both are equal to the Hoffman bound/Lovasz theta of the complement since they are SRGs). In practice it seems that almost all are cores. I tested around 80,000 SRGs from Ted Spence's webpage and all but 79 were cores.
\end{shameless plug}
A: Say that a graph is strongly critical if deletion of any vertex or edge decreases its chromatic number.
Take any two nonisomorphic $k$-strongly critical graphs $G$ and $H$ with the same number of vertices (e.g., the Mycielski construction on a triangle and the Hajos construction on two copies of $K_4$, for $k=4$). Their disjoint union fits the goal, since there are no homomorphisms from $G$ to $H$ and vice versa.
