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?



Critical graphs and endomorphisms
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}


