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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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}

Improve this answer
$\endgroup$
2
  • $\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
    Commented Aug 31, 2016 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
    Commented Aug 31, 2016 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .