Hedetniemi's Conjecture for Uncountable Complementary Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.08027
curl -X POST /api/v1/records/arxiv/2610.08027/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08027/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'