Hedetniemi's Conjecture

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Coloring
	» » Vertex coloring

Keywords:	categorical product
	coloring
	homomorphism
	tensor product

Recomm. for undergrads: no

Posted	by:	mdevos
	on:	May 25th, 2008

Conjecture If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$ .

Here $G \times H$ is the tensor product (also called the direct or categorical product) of $G$ and $H$ .

This beautiful and seemingly innocent conjecture asserts a deep and important property of graph coloring. It is undoubtedly one of the most significant unsolved problems in graph coloring and graph homomorphisms.

We write $G \rightarrow H$ if there is a homomorphism from $G$ to $H$ . The graph $G \times H$ has a two natural projection maps (projecting onto either the first or second coordinate), and these maps are homomorphisms to $G$ and to $H$ . So, in short, $G \times H \rightarrow G$ and $G \times H \rightarrow H$ . A graph is $n$ -colorable if and only if it has a homomorphism to $K_n$ . Combining this with the transitivity of $\rightarrow$ we find that $\chi(G \times H) \le \min\{ \chi(G), \chi(H) \}$ (indeed, if $\chi(G) = n$ , then $G \times H \rightarrow G$ and $G \rightarrow K_n$ , so $G \times H \rightarrow K_n$ - equivalently, $G \times H$ is $n$ -colorable). So, the hard direction of Hedetniemi's Conjecture is to prove that $\chi(G \times H) \ge \min \{ \chi(G), \chi(H) \}$ .

Let's define $P(n)$ to be the proposition that $\chi(G \times H) \ge n$ whenever $\chi(G) \ge n$ and $\chi(H) \ge n$ . Then the above conjecture is equivalent to the statement that $P(n)$ holds for every positive integer $n$ . Now $P(1)$ holds trivially and $P(2)$ follows from the observation that the product of two graphs each of which contains an edge is a graph which contains an edge. The next case is quite easy too, if $\chi(G) \ge 3$ and $\chi(H) \ge 3$ , then both $G$ and $H$ contain an odd cycle. Since the product of two odd cycles contains an odd cycle, this shows $\chi(G \times H) \ge 3$ . The next case up, $P(4)$ was proved by El-Zahar and Sauer by way of a beautiful argument. It is open for all higher values.

A key tool in the proof of El-Zahar and Sauer is the use of exponential graphs. For any pair of graphs $G, H$ the exponential graph $G^H$ is a graph whose vertex set consists of all mappings $f: V(H) \rightarrow V(G)$ . Two vertices $f,g$ are adjacent if $f(x)g(y)$ is an edge of $G$ whenever $xy$ is an edge of $H$ . It is easy to see the relevance of $K_n^G$ to this problem. If we have an $n$ -coloring $f$ of $G \times H$ , then for every vertex $x \in V(H)$ , there is a mapping $f_x : V(G) \rightarrow V(K_n)$ given by $f_x(v) = f(v,x)$ . This associates each $x \in V(H)$ with a vertex in $K_n^G$ . Now it is easy to verify that whenever $x,y$ are adjacent vertices in $H$ , the maps $f_x$ and $f_y$ are adjacent in $K_n^G$ . Rather more surprisingly, Hedetniemi's conjecture may be reformulated as follows:

Conjecture (version 2 of Hedetniemi) If $\chi(G) > n$ , then $K_n^G$ is $n$ -colorable.

The following conjecture asserts that Hedetniemi's conjecture still holds with circular chromatic number instead of the usual chromatic number. Here $\chi_c(G)$ is the circular chromatic number of $G$ . Since $\chi(G) = \lceil \chi_c(G) \rceil$ this is a generalization of the original conjecture.

Conjecture (Zhu) If $G$ and $H$ are finite simple graphs then $\chi_c(G \times H) = \min\{ \chi_c(G), \chi_c(H) \}$ .

A graph $G$ has circular chromatic number $\frac{n}{k}$ for positive integers $n,k$ if and only if $G$ has a homomorphism to the graph $K_{n/k}$ . This is a graph whose vertex set consists of $n$ vertices cyclically ordered, with two vertices adjacent if they are distance $\ge k$ apart in the cyclic ordering. So again, we may state this conjecture in terms of homomorphisms to graphs of the form $K_{n/k}$ . More generally, let us call a graph $K$ multiplicative if $G \times H \rightarrow K$ implies either $G \rightarrow K$ or $H \rightarrow K$ . Now Hedetniemi's conjecture asserts that every $K_n$ is multiplicative and Zhu's conjecture asserts that every $K_{n/k}$ is multiplicative. With this terminology, El-Zahar and Sauer proved that $K_3$ is multiplicative. A clever generalization of their argument due to Haggkvist, Hell, Miller and Neumann Lara showed that every odd cycle is multiplicative. Recently, Tardif bootstrapped this theorem with the help of a couple of interesting operators on the category of graphs to prove the $K_{n/k}$ is multiplicative whenever $n/k < 4$ . Ignoring trivial cases and equivalences, these are essentially the only graphs known to be multiplicative.

It might be tempting to hope that all graphs are multiplicative, but this is false. To construct a non-multiplicative graph, take two graphs $G,H$ with the property that $G \not\rightarrow H$ and $H \not\rightarrow G$ (for instance $K_3$ and the Grotzsch Graph). Now $G \times H$ is not multiplicative since $G \not\rightarrow G \times H$ and $H \not\rightarrow G \times H$ , but $G \times H \rightarrow G \times H$ . It seems that there is no general conjecture as to what graphs are multiplicative. Some other Cayley graphs look like reasonable candidates to me (M. DeVos), but I haven't any evidence one way or the other.

Poljak and Rodl defined the function $f(n) = \min \{ \chi(G \times H) : \chi(G) = n = \chi(H) \}$ . So, Hedetniemi's conjecture is equivalent to $f(n) = n$ . Using an interesing inequality relating the chromatic number of a digraph $D$ to the chromatic number of a type of line graph of $D$ , they were able to prove the following quite surprising result: Either $f$ is bounded by $9$ or $\lim_{n \rightarrow \infty} f(n) = \infty$ .

There are a number of interesting partial results not mentioned here, and the reader is encouraged to see the survey article by Zhu.

add new comment

Yaroslav Shitov made some

On March 1st, 2020 Anonymous says:

Yaroslav Shitov made some significant breakthroughs in this area - https://arxiv.org/abs/1905.02167.

Lovasz Theta

On February 27th, 2013 Anonymous says:

I believe that Robert Samal has conjectured a version of this for the Lovasz $\vartheta$ function, i.e. that $\bar{\vartheta}(G \times H) = \min\{\bar{\vartheta}(G), \bar{\vartheta}(H)\}$ where $\bar{\vartheta}(G) := \vartheta(\overline{G})$ . I can't find it in the Garden, but it is in this presentation by Samal: http://iuuk.mff.cuni.cz/research/cmi/cmi-I-Samal.pdf

Re: Lovasz Theta

On July 23rd, 2013 Robert Samal says:

In fact, for the Lovasz $\vartheta$ function (of the complement of the graph) it is a theorem, see arXiv:1305.5545.

Fractional version is true

On October 18th, 2011 Anonymous says:

It is probably worth mentioning that Zhu recently proved the fractional version of this conjecture: that $\chi_f(G \times H) = \min\{\chi_f(G),\chi_f(H)\}$ .

Xuding Zhu, The fractional version of Hedetniemi’s conjecture is true, European Journal of Combinatorics, Volume 32, Issue 7, October 2011, Pages 1168-1175, ISSN 0195-6698, 10.1016/j.ejc.2011.03.004. (http://www.sciencedirect.com/science/article/pii/S0195669811000552)

Very interesting Conjecture.

On November 8th, 2010 Jon Noel says:

Very interesting Conjecture.

Open Problem Garden

Hedetniemi's Conjecture

Yaroslav Shitov made some

Lovasz Theta

Re: Lovasz Theta

Fractional version is true

Very interesting Conjecture.

Comment viewing options

Navigate

Recent Activity