Given (finite, simple) graphs $G$, $H$ and $K$ and a homomorphism $$ G+K\to H+K $$ where $+$ denotes the join, does it follow that there also exists a graph homomorphism $G\to H$?
If this is known, I'd also appreciate a reference.
$\begingroup$
$\endgroup$
6
asked Sep 18, 2017 at 14:36
-
1$\begingroup$ Worth pointing out: we have (the inequality $\leq$ follows by retaining optimal colorings, while the inequality $\geq$ follows because if $\chi(G+K) < \chi(G) + \chi(K)$, then choose any such hypothetical coloring and notice that one of the two summands then would be colored with less colors than its chromatic number allows, which is impossible) the equality $\chi(G+K) = \chi(G) + \chi(K)$. Moreover, in general, if $X\to Y$, then $\chi(X)\leq\chi(Y)$. We now put this together. If $G+K\to H+K$, then $\chi(G)+\chi(K) = \chi(G+K)\leq\chi(H+K)=\chi(H)+\chi(K)$, hence $\chi(G)\leq\chi(H)$. So [..] $\endgroup$– Peter HeinigCommented Sep 18, 2017 at 15:35
-
$\begingroup$ [..] we have proved that if $G+K\to H+K$, then $\chi(G)\leq \chi(H)$, hence $G\to K^{{\Large\chi(H)}}$. It follows that: if there is a counterexample to the implication you are asking about, then $H$ must be non-complete. Have you searched around among small such instances? $\endgroup$– Peter HeinigCommented Sep 18, 2017 at 15:37
-
1$\begingroup$ @PeterHeinig: Good point about the chromatic numbers. I guess the same applies to the clique numbers, i.e. $\omega(G)\leq\omega(H)$, so that $G\to H$ also follows when $G$ is complete. So far, I haven't done much of a search on small instances. $\endgroup$– Tobias FritzCommented Sep 18, 2017 at 15:50
-
$\begingroup$ @IlyaBogdanov: Sure. I was assuming that finiteness would be clear from the context, but I'll make it explicit in the question. $\endgroup$– Tobias FritzCommented Sep 18, 2017 at 15:51
-
1$\begingroup$ To repeat a comment to a deleted answer. The case of $K$ complete is in fact much easier, since the vertices of $K$ in both $G+K$ and $H+K$ are dominating (=connected to everyone elde). Since the image of a dominating vertex cannot be anyone else's image, and all dominating vertices can be permuted via automorphisms, we may simply assume that the vertices of $K$, and only them, are mapped to the vertices of $K$. $\endgroup$– Ilya BogdanovCommented Sep 18, 2017 at 17:24
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
If $|K|=\infty$, then this is false, as a counterexample $G=K_2$, $H=K_1$, $K=K_\infty$ shows.
Let us prove that the claim is true if $K$ is finite (with no such assumption for $G$ and $H$). Induction on $|K|$; if $|K|=0$, the claim is trivial.
For the inductive step, consider a homomorphism $\psi\colon G+K\to H+K$. Set $G_1=\psi(G)\cap K$, $K_1=\psi(K)\cap K$, $H_1=\psi(K)\cap H$. If $G_1=\varnothing$, then $\psi\big|_G$ is a required homomorphism $G\to H$. So now we assume that $|G_1|>0$.
Each vertex of $G_1$ is connected with each of $K_1$ since $\psi$ is a homomorphism (thus in particulat $|K_1|<|K|$). Each vertex of $H_1$ is connected with each of $K_1$ by the definition of join. Thus, the induced subgraphs on $G_1\cup K_1(\subseteq K)$ and $H_1\cup K_1$ are isomorphic to $G_1+K_1$ and $H_1+K_1$, respectively. So $\psi\big|_{G_1\cup K_1}$ provides a homomorphism $G_1+K_1\to H_1+K_1$ which by the induction hypothesis implies the existence of a homomorphism $\varphi\colon G_1\to H_1$.
Finally, set $M=\psi(G)\cap H$. Each vertex of $M$ is connected with each of $K_1$, since $\psi$ is a homomorphism. Thus the map $\eta\colon G\to H$, $$ \eta(g)=\begin{cases} \psi(g), &\psi(g)\in M;\\ \varphi(\psi(g)), &\psi(g)\in G_1 \end{cases} $$ is a sought homomorphism. The step is proved.
-
$\begingroup$ This perfectly answers the question. I'd still be grateful for pointers to the literature where a proof may already have appeared. $\endgroup$ Commented Sep 18, 2017 at 17:19