2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ I should point out that I don't actually know how often a strongly regular graph is not critical, but my guess would be that it is a common occurrence. I just quickly checked about 20,000 of the SRGs with parameters (36,20,10,12), and at least 18,000 of these are not critical. $\endgroup$ – David Roberson Aug 31 '16 at 13:20
  • 1
    $\begingroup$ Probably also worth mentioning that it is actually known that almost all graphs are cores. In fact almost all graphs have only the identity map as an endomorphism. There is a proof in the book Graphs and Homomorphisms by Hell and Nesetril. If I had to guess I would say that almost all graphs are not critical. $\endgroup$ – David Roberson Aug 31 '16 at 13:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.