In this question, a **graph** is a finite, undirected graph without loops or multiple edges, and a **colouring** of a graph is a proper vertex colouring. The **product** $G \times H$ of graphs $G$ and $H$ is the graph whose vertex-set is the product of the vertex-sets of $G$ and $H$ and whose edge-set is the product of the edge-sets of $G$ and $H$, with the obvious incidence relation.

Let $G$ and $H$ be graphs. Any $n$-colouring of $G$ gives rise to an $n$-colouring of $G \times H$: just paint $(x, y)$ the same colour as $x$. (Or, if you prefer, an $n$-colouring of a graph is just a homomorphism into the complete graph $K_n$, so we can compose the colouring $G \to K_n$ with the projection $G \times H \to G$ to obtain a colouring $G \times H \to K_n$.) Similarly, any $n$-colouring of $H$ gives rise to an $n$-colouring of $G \times H$. Let us say that a colouring of $G \times H$ arising in one of these two ways is **obtained by projection**.

The previous paragraph makes it clear that $\chi(G \times H) \leq \min\{ \chi(G), \chi(H) \}$, where $\chi$ means chromatic number. Hedetniemi's conjecture states that this is an equality. In other words, it says that there are no colourings of a product more economical than those obtained by projection. My question:

Let $G$ and $H$ be graphs. Is every colouring of $G \times H$ with $\chi(G \times H)$ colours obtained by projection?

The answer can't be known to be yes, unless I've missed some news, since that would imply Hedetniemi's conjecture. But perhaps the answer is no, or perhaps it's known that this apparently stronger conjecture would actually be implied by Hedetniemi's original conjecture.

**Edit** Assume the graphs are connected, otherwise the answer is trivially no. (E.g. consider $(K_2 \sqcup K_2) \times K_2$.)

2more comments