When is the direct product of two cores itself a core?

155 Views Asked by At

Given graphs $X$ and $Y$, a graph homomorphism $f : X \to Y$ is a function $f : V(X) \to V(Y)$ such that if $uv \in X$, then $f(u)f(v) \in E(Y)$—that is, it is a function of the vertices mapping edges to edges. Let $X \to Y$ mean there exists a graph hom with domain $X$ and codomain $Y$. Say $X$ and $Y$ are hom-equivalent ($X \leftrightarrow Y$) if $X \to Y$ and $Y \to X$, and say they are hom-incomparable if $X \not\to Y$ and $Y \not\to X$. For instance, if $G$ is the Grötzsch graph, then $G$ and $K_3$ are hom-incomparable.

$\to$ is a preorder on the graphs, and in fact the hom-equivalence classes form not just a poset, but a lattice, with disjoint union $\sqcup$ as the join operation and the direct product of graphs $\times$ as the meet.

Each hom-equivalence class has a unique-up-to-isomorphism representative graph called a core, with the property that $X$ is a core iff $\def\End{\text{End}}\def\Aut{\text{Aut}}\End(X) = \Aut(X)$ (one of many equivalent definitions). It can be shown that two graphs are hom-equivalent if they have isomorphic cores. So I'm wondering how nicely the lattice operations play with cores.

I can show that if $X \to Y$, then $X \sqcup Y \leftrightarrow Y$ and $X \times Y \leftrightarrow X$ so neither join nor meet is a core. However, if $X$ and $Y$ are hom-incomparable cores, I can show that $X \sqcup Y$ is a core. (Proof: $X$ and $Y$ are incomparable, so any endo of $X \sqcup Y$ has to map each 'component' to itself, and since $X$ and $Y$ are cores, the endos are autos.) My question:

If $X$ and $Y$ are hom-incomparable cores, then is $X \times Y$ also always a core?

My intuition says yes, because if there is an $f \in \End(X \times Y)$ that isn't bijective, then there should be some reflection of that under the projections. But I have no idea how to approach.