MathDB

Complementary Hedetniemi problem for infinite graphs

Does ZFC prove that there exists a simple graph G=(V,E)G=(V,E) such that χ(G)≥ω1\chi(G)\geq\omega_1, χ(G‾)≥ω1\chi(\overline{G})\geq\omega_1, and χ(G×G‾)=ω\chi(G\times\overline{G})=\omega, where G×G‾G\times\overline{G} is the categorical product with vertex set V×VV\times V and (u,v)(u,v) adjacent to (u′,v′)(u',v') exactly when uu′∈E(G)uu'\in E(G) and vv′∈E(G‾)vv'\in E(\overline{G})?

References

Primary source

arXiv

Additional references

infinite-graph-theoryset-theory
Posted · edited

Progress summary

Refreshed
Claimed progress

A new preprint gives a conditional example at the first uncountable size, but does not settle whether an example exists in ordinary set theory.

The problem asks when an infinite analogue of Hedetniemi’s phenomenon can occur. Existing work shows such failures in particular set-theoretic universes, while existence in ZFC\mathrm{ZFC} remains unresolved.

Known results

  • Hajnal constructed, for every infinite cardinal λ\lambda, graphs of size and chromatic number λ+\lambda^+ whose tensor product has chromatic number λ\lambda.
  • Soukup obtained a model of ZFC+GCH\mathrm{ZFC}+\mathrm{GCH} with graphs of size and chromatic number ℵ2\aleph_2 whose tensor product is countably chromatic.
  • Rinot (2017) showed that ◊λ\Diamond_\lambda yields graphs of size and chromatic number λ+\lambda^+ with countably chromatic tensor product.

October 2026 conditional construction

A preprint by Lajos Soukup claims that any such example must have ω1\omega_1 vertices, and constructs one under ◊\Diamond, with a c.c.c.\mathrm{c.c.c.} forcing construction as well. This is substantive claimed progress, but it leaves existence in ZFC\mathrm{ZFC} open and has no independent verification in the retrieved sources.

Current status (as of October 2026): Conditional examples and a claimed minimum scale of ω1\omega_1 are available, but existence in ZFC\mathrm{ZFC} remains open.

Sources

Solutions 0

No solutions have been posted yet.