Zhu's conjecture for categorical products of hypergraphs

At least 11 years old · documented by

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×V′V\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.

References

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.