4
$\begingroup$

Let $G,H$ be simple undirected graphs without loops such that there are graph homomorphisms $f_1:G\to H$ and $f_2: H\to G$.

An easy argument shows that we have $\chi(G) = \chi(H)$, even for graphs with infinite chromatic number.

What other conclusions can be made about $G, H$ if we know that there are graph homomorphisms in either direction?


Note: There need not be a graph homomorphism between two graphs. For instance, $\textrm{Hom}(G,K_2)=\emptyset$ iff $\chi(G) > 2$.

$\endgroup$
1
  • 1
    $\begingroup$ I don't really know anything about this question, but I found this on Wikipedia. $\endgroup$ Dec 1 '14 at 13:01
6
$\begingroup$

Let $\omega (G)$ be the clique number of $G$ i.e. the largest $n$ such that $G$ contains $K_n$ as a subgraph; this is the same as the largest $n$ such that a homomorphism $K_n \rightarrow G$ exists. By composing $K_n \rightarrow G \xrightarrow{f_1} H$ we obtain $\omega (G) \leq \omega (H)$ and similarly in the other direction, so that the graphs also have the same clique number.

Two graphs such that each has a homomorphism to the other are homomorphically equivalent. This is an equivalence relation on the set of graphs, and the minimal representative of each equivalence class is called a core, which is unique up to isomorphism. Every endomorphism of a core is an isomorphism.

Thus $G$ and $H$ above have the same core, so if you further suppose $\chi (G) = \omega (G)=n$ then the core of $G$ and $H$ is $K_n$.

$\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.