Zhu's conjecture for categorical products of hypergraphs

Let G=(V,E)\mathcal{G}=(V,E) and G=(V,E)\mathcal{G}'=(V',E') be hypergraphs. Their categorical product G×G\mathcal{G}\times\mathcal{G}' has vertex set V×VV\times V' and edges whose projections onto the two factors are edges of the respective hypergraphs. Let χ(G)\chi(\mathcal{G}) denote the chromatic number, the least number of colors in a proper coloring with no monochromatic edge. Zhu's conjecture. The categorical product of two hypergraphs satisfies

χ(G×G)=min{χ(G),χ(G)}.\chi(\mathcal{G}\times\mathcal{G}')=\min\{\chi(\mathcal{G}),\chi(\mathcal{G}')\}.

The conjecture is presented as the hypergraph generalization of Hedetniemi's conjecture. The paper states that it proves the conjecture for usual Kneser hypergraphs of the same rank and obtains a more general lower bound for products of Kneser hypergraphs of common rank; the unrestricted hypergraph statement is not claimed to be resolved here.

Sources & referencesView supporting material

Primary source

Hossein Hajiabolhassan and Frédéric Meunier, “Hedetniemi's conjecture for Kneser hypergraphs”, arXiv:1410.3021 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.