{"id":"arxiv/2610.08027","url":"https://arxiv.org/abs/2610.08027","tags":["math.CO","math.LO"],"score":0,"title":"Hedetniemi's Conjecture for Uncountable Complementary Graphs","domain":"math.CO","source":"arxiv","authors":["Lajos Soukup"],"reviews":0,"subject":"math.CO","summary":"We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph $G$ and its complement $\\overline{G}$ are both uncountably chromatic while their categorical product is countably chromatic, then $|V(G)|=ω_1$. Assuming $\\diamondsuit$, we construct a graph $G$ on $ω_1$ such that $χ(G)=χ(\\overline{G})=ω_1$ and $χ(G\\times\\overline{G})=ω$; the construction uses two suitably chosen minimal Countryman lines. We also define a c.c.c. forcing of cardinality $ω_1$ that adds a graph with the same properties. It remains open whether ZFC alone proves the existence…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}