In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that
χ ( G × H ) = min { χ ( G ) , χ ( H ) } . {\displaystyle \chi (G\times H)=\min\{\chi (G),\chi (H)\}.}
Here χ ( G ) {\displaystyle \chi (G)} denotes the chromatic number of an undirected finite graph G {\displaystyle G} . The inequality χ(G × H) ≤ min {χ(G), χ(H)} is easy: if G is k-colored, one can k-color G × H by using the same coloring for each copy of G in the product; symmetrically if H is k-colored. Thus, Hedetniemi's conjecture amounts to the assertion that tensor products cannot be colored with an unexpectedly small number of colors. A counterexample to the conjecture was discovered by Yaroslav Shitov (2019) (see Kalai 2019), thus disproving the conjecture in general.
Known cases Any graph with a nonempty set of edges requires at least two colors; if G and H are not 1-colorable, that is, they both contain an edge, then their product also contains an edge, and is hence not 1-colorable either. In particular, the conjecture is true when G or H is a bipartite graph, since then its chromatic number is either 1 or 2. Similarly, if two graphs G and H are not 2-colorable, that is, not bipartite, then both contain a cycle of odd length. Since the product of two odd cycle graphs contains an odd cycle, the product G × H is not 2-colorable either. In other words, if G × H is 2-colorable, then at least one of G and H must be 2-colorable as well. 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 particular, the conjecture is true whenever G or H is 4-colorable (since then the inequality χ(G × H) ≤ min {χ(G), χ(H)} can only be strict when G × H is 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.
Weak Hedetniemi Conjecture The following function (known as the Poljak-Rödl function) measures how low the chromatic number of products of n-chromatic graphs can be.
f ( n ) = min { χ ( G × H ) : χ ( G ) = χ ( H ) = n } {\displaystyle f(n)=\min\{\chi (G\times H)\colon \chi (G)=\chi (H)=n\}}
Hedetniemi's conjecture is then equivalent to saying that f(n) = n. The Weak Hedetniemi Conjecture instead states merely that the function f(n) is unbounded. In other words, if the tensor product of two graphs can be colored with few colors, this should imply some bound on the chromatic number of one of the factors. The main result of (Poljak & Rödl 1981), independently improved by Poljak, James H. Schmerl, and Zhu, states that if the function f(n) is bounded, then it is bounded by at most 9. Thus a proof of Hedetniemi's conjecture for 10-chromatic graphs would already imply the Weak Hedetniemi Conjecture for all graphs.
Multiplicative graphs The conjecture is studied in the more general context of graph homomorphisms, especially because of interesting relations to the category of graphs (with graphs as objects and homomorphisms as arrows). For any fixed graph K, one considers graphs G that admit a homomorphism to K, written G → K. These are also called K-colorable graphs. This generalizes the usual notion of graph coloring, since it follows from definitions that a k-coloring is the same as a Kk-coloring (a homomorphism into the complete graph on k vertices). A graph K is called multiplicative if for any graphs G, H, the fact that G × H → K holds implies that G → K or H → K holds. 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. The above known cases are equivalent to saying that K1, K2, and K3 are multiplicative. The case of K4 is widely open. 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. Later, Tardif (2005) proved more generally that all circular cliques Kn/k with n/k < 4 are multiplicative. In terms of the circular chromatic number χc, this means that if χc(G×H) < 4, then χc(G×H) = min { χc(G), χc(G)} . Wrochna (2017) has shown that square-free graphs are multiplicative. Examples of non-multiplicative graphs can be constructed from two graphs G and H that are not comparable in the homomorphism order (that is, neither G→H nor H→G holds). 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.
Exponential graph Since the tensor product of graphs is the category-theoretic product in the category of graphs (with graphs as objects and homomorphisms as arrows), the conjecture can be rephrased in terms of the following construction on graphs K and G. The exponential graph KG is the graph with all functions V(G) → V(K) as vertices (not only homomorphisms) and two functions f,g adjacent when
… excerpt ends here. Continue reading the full article.
