Erdős–Hajnal property for {C₈, C̄₈}
Erdős-Hajnal property for $\{C_8, \overline{C_8}\}$ · arXiv:2102.04994
Status open high confidence
The source paper (arXiv:2102.04994) proves that $\{C_6, \overline{C_6}\}$ and $\{C_7, \overline{C_7}\}$ each have the Erdős-Hajnal property, but explicitly leaves open whether the same holds for $\{C_8, \overline{C_8}\}$. A wide search of the post-2021 literature — including a survey of new Erdős-Hajnal results through 2024–2025 and a review of the key follow-up paper arXiv:2307.06455 — found no work resolving this question. The conjecture remains open as of May 2026.
Reviewer notes. No follow-up paper resolving the conjecture was found. The conjecture was posted in 2021 as an explicit open problem; the related arXiv:2307.06455 ('New graphs with the Erdős-Hajnal property') does not mention C8. Absence of evidence is strong given the conjecture's specificity and the breadth of the search.
Context
The paper proves that $\{C_6, \overline{C_6}\}$ (result 1.7) and $\{C_7, \overline{C_7}\}$ (result 1.8) each have the Erdős-Hajnal property. The authors remark that it would be nice to know whether the same holds for $\{C_8, \overline{C_8}\}$, but that this remains open.
Notes. Stated in running prose as 'it would be nice to know if the same is true for $\{C_8,\overline{C_8}\}$, but this remains open'; no formal theorem environment.
Source paper
Erdos-Hajnal for graphs with no 5-hole
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2021-02-09
https://arxiv.org/abs/2102.04994
PDF source