Hedetniemi's conjecture

In particular, the conjecture is true when G or H is a bipartite graph, since then its chromatic number is either 1 or 2.

The next case was proved long after the conjecture's statement, by El-Zahar & Sauer (1985): if the product G × H is 3-colorable, then one of G or H must also be 3-colorable.

In the remaining cases, both graphs in the tensor product are at least 5-chromatic and progress has only been made for very restricted situations.

As with classical colorings, the reverse implication always holds: if G (or H, symmetrically) is K-colorable, then G × H is easily K-colored by using the same values independently of H. Hedetniemi's conjecture is then equivalent to the statement that each complete graph is multiplicative.

On the other hand, the proof of El-Zahar & Sauer (1985) has been generalized by Häggkvist et al. (1988) to show that all cycle graphs are multiplicative.

In this case, letting K=G×H, we trivially have G×H→K, but neither G nor H can admit a homomorphism into K, since composed with the projection K→H or K→G it would give a contradiction.

These properties allow to conclude that the multiplicativity of K is equivalent (El-Zahar & Sauer 1985) to the statement: In other words, Hedetniemi's conjecture can be seen as a statement on exponential graphs: for every integer k, the graph KkG is either k-colorable, or it contains a loop (meaning G is k-colorable).

Generalized to directed graphs, the conjecture has simple counterexamples, as observed by Poljak & Rödl (1981).

However, the Weak Hedetniemi Conjecture turns out to be equivalent in the directed and undirected settings (Tardif & Wehlau 2006).

A similar equality for the cartesian product of graphs was proven by Sabidussi (1957) and rediscovered several times afterwards.

Duffus, Sands & Woodrow (1985) introduced two stronger conjectures involving unique colorability.