# Hedetniemi conjecture

For two graphs $A$ and $B$ (cf. Graph), their categorial product $A\times B$ is the graph with vertex set $V(A\times B)=V(A)\times V(B)$ while an edge $(a_0,b_0)$ is adjacent to an edge $(a_1,b_1)$ if and only if $a_0$ is adjacent to $a_1$ and $b_0$ is adjacent to $b_1$. If the graph $A$ has a good $n$-colouring $\gamma$ (cf. Graph colouring), then $A\times B$ has a good $n$-colouring $\gamma^*$, given by $\gamma^*(a,b)=\gamma(a)$. As this statement also holds for good $n$-colourings of $B$, it follows that the chromatic number $\chi(A\times B)\leq\min\{\chi(A),\chi(B)\}$. Hedetniemi's conjecture, [a1], is that for all finite graphs $A$ and $B$:

$$\chi(A\times B)=\min\{\chi(A),\chi(B)\}.$$

The corresponding statement for infinite graphs is not true [a2], but little is known about the relationship between the cardinalities of the chromatic numbers of $A$ and $B$ and the chromatic number of $A\times B$.

It is obvious that the chromatic number of the product of two $2$-chromatic graphs is $2$. L. Lovász [a3] showed that the chromatic number of the product of two $3$-chromatic graphs is $3$ and in [a4] it is proven that the chromatic number of the product of two $4$-chromatic graphs is $4$. It is not known whether the chromatic number of the product of two $n$-chromatic graphs is always $n$ for any $n\geq5$. The lack of understanding of this problem is even more embarrassing than that.

Let $f(n)$ be the largest number such that whenever $A$ and $B$ are two $n$-chromatic graphs, then the chromatic number of $A\times B$ is larger than or equal to $f(n)$. Clearly, if $n\geq4$, then $4\leq f(n)\leq n$ and Hedetniemi's conjecture says that $f(n)=n$. About $f(n)$ it is only known that either $f(n)\leq9$ for all $n$ or $f(n)$ is unbounded, [a5] and [a6].

Write $A\mapsto B$ if there is a homomorphism from the graph $A$ to the graph $B$ (a function from $A$ to $B$ which preserves the edges). Write $A\not\mapsto B$ if there is no homomorphism from $A$ to $B$. A graph $M$ is called multiplicative, [a7], [a8], if $A\not\mapsto M$ and $B\not\mapsto M$ imply $A\times B\not\mapsto M$. Note that a graph $A$ has a good $n$-colouring if and only if $A\mapsto K_n$. Hence Hedetniemi's conjecture is equivalent to asking whether the complete graph $K_n$ (cf. also Graph) is multiplicative.

Two graphs $A$ and $B$ are equivalent, $A\sim B$, if $A\mapsto B$ and $B\mapsto A$. It is not difficult to check that the equivalence classes of finite graphs form a distributive lattice under the order relation $\mapsto$ and that a graph is multiplicative if and only if it is a meet-irreducible element of this lattice. Once this general setting of the problem has been realized, it is not difficult to see that Hedetniemi's conjecture has a natural generalization, [a8], to the problem of finding the meet-irreducible elements in the distributive lattices of various types of relational structures. This line of investigation leads to a setting in topos theory and, to a certain extent, in logic, [a9].

Of course this introduces the even more general task of trying to understand the distributive lattice of, say, all finite relational structures of a given type and, in connection with this, the problem of deciding whether there is a homomorphism from a given relational structure to another one of the same type. In this context one of the more interesting types of relational structures are finite directed graphs, [a10]. Multiplicative partially ordered sets have been investigated in [a11].

For graphs, Hedetniemi's conjecture has been confirmed for various special cases and several interesting observations have been made. See [a12], [a13], [a14]. For a general discussion of graph products, see [a15].

How to Cite This Entry:
Hedetniemi conjecture. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hedetniemi_conjecture&oldid=38984
This article was adapted from an original article by N.W. Sauer (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article