Open Problem Garden - Hedetniemi's Conjecture - Comments

Yaroslav Shitov made some (re: Hedetniemi's Conjecture)

Anonymous — Sun, 01 Mar 2020 15:21:26 +0100

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

Re: Lovasz Theta (re: Hedetniemi's Conjecture)

Robert Samal — Tue, 23 Jul 2013 21:42:00 +0200

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

Lovasz Theta (re: Hedetniemi's Conjecture)

Anonymous — Wed, 27 Feb 2013 21:58:11 +0100

I believe that Robert Samal has conjectured a version of this for the Lovasz function, i.e. that where . 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

Fractional version is true (re: Hedetniemi's Conjecture)

Anonymous — Tue, 18 Oct 2011 03:40:33 +0200

It is probably worth mentioning that Zhu recently proved the fractional version of this conjecture: that .

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. (re: Hedetniemi's Conjecture)

Jon Noel — Mon, 08 Nov 2010 22:55:20 +0100

Very interesting Conjecture.

Hedetniemi's Conjecture

mdevos — Sun, 25 May 2008 01:55:56 +0200

Author(s): Hedetniemi

Subject: Graph Theory » Coloring » Vertex coloring

Conjecture If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .