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

  • $\begingroup$ Dear Tom, as far as I know it is wide open. $\endgroup$
    – Gil Kalai
    Commented Nov 10, 2013 at 15:26
  • $\begingroup$ @Gil: thanks. Is this strong form something that's been discussed much in the literature? $\endgroup$ Commented Nov 10, 2013 at 15:30
  • $\begingroup$ Tom, ahh I missed your strong version. I suppose by minimal coloring you mean a coloring with minimum number of colors, right? I find your strong version hard to believe. $\endgroup$
    – Gil Kalai
    Commented Nov 10, 2013 at 18:07
  • 2
    $\begingroup$ Did you check the product of two odd cycles? $\endgroup$
    – Gil Kalai
    Commented Nov 10, 2013 at 18:09
  • $\begingroup$ @GilKalai, you're quite right, that's exactly the thing to do. There's a colouring of $C_3 \times C_5$ that shows that the answer is no. I'll write it up into a community wiki answer in a minute. (And yes, by "minimal colouring" I meant what you said.) $\endgroup$ Commented Nov 10, 2013 at 18:31

1 Answer 1


The answer is no. In the comments, Gil Kalai suggested looking at products of two odd cycles, and indeed, this yields a counterexample.

Consider $C_3 \times C_5$, where $C_n$ denotes the $n$-cycle. This has chromatic number $3$, and there is a 3-colouring given by $$ \begin{pmatrix} 1&3&1&2&3\\ 1&2&1&2&3\\ 1&2&1&2&3 \end{pmatrix} $$ (in what I hope is obvious notation). This is plainly not obtained by projection.

In fact, this is also a counterexample to a weaker form of this strong form of Hedetniemi's conjecture: that every colouring of $G \times H$ by $\chi(G \times H)$ colours is obtained by projection after some automorphism of $G \times H$. For any such colouring of $C_3 \times C_5$ has either 5 of each colour or 3 of one and 6 of each of the other two; but neither is the case for the colouring shown above.

  • $\begingroup$ Very nice! Still, I tend to agree with Tardif who wrote in his "40 years later" survey, that Hedetniemi's conjecture is saying that lifted colorings are essentially the best way to color the product. But what do we really mean by "best" :)? $\endgroup$
    – saf
    Commented Nov 17, 2013 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.