Skip to content
DraconiticResearch
Search Sources API
181,686 studies31 sourcesUpdated 4 min ago
PreprintCC BY 4.0arXiv

Hedetniemi's Conjecture for Uncountable Complementary Graphs

  • Lajos Soukup
Open at sourcePDFDOICite

Abstract

We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph G and its complement 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)=χ(G̅)=ω1 and χ(G×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 of such a graph.

Related

  1. Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
    Julius A. Zeiss
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A counterexample to the quantum Hedetniemi conjecture
    Julius A. Zeiss
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv
  3. Bicyclic Graphs with Maximum Complementary Diminished Sombor Index
    Nicholas Smirnov
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeometry & topologyDOAJ
  4. There are no nontrivial chordal square-complementary graphs
    Pierre Aboulker, Martin Milanič, Peter Muršič +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Fractional revival in complementary prisms of graphs
    Sarojini Mohapatra, Hiranmoy Pal
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{soukup2026hedetniemis,
  title = {{Hedetniemi's Conjecture for Uncountable Complementary Graphs}},
  author = {Lajos Soukup},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08027},
  eprint = {2610.08027},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08027},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Hedetniemi's Conjecture for Uncountable Complementary Graphs
AU  - Lajos Soukup
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.08027
UR  - https://arxiv.org/abs/2610.08027
AB  - We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph G and its complement 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)=χ(G̅)=ω_1 and χ(G×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 of such a graph.
ER  -