The Erdos-Hajnal High-Girth Subgraph Conjecture

Erdos and Hajnal asked whether $h_r(G) = \max\{\chi(H) : H \subseteq G,\ \mathrm{girth}(H) \ge r\}$ tends to infinity as $\chi(G)$ does, for every fixed $r \ge 4$ . It does in every fixed polynomial edge-density regime.

Result: Proved(see note)
Status: Partial result
AI contribution: AI co-developed
Method: Argument
Field: Graph theory
Posed by: Paul Erdos, Andras Hajnal
Year posed: 1966
Years open: 60y
Solved: 2026-06-16
Model: ChatGPT
Vendor: OpenAI
Collaborators: Eric Li
Verification: Unreviewed
Publication: Preprint
Significance: 25 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

in polynomial edge-density regimes; the general question remains open

What the AI did

The declaration says ChatGPT was used for ideation and formalization during preparation, with the author responsible for the mathematics. Part of the same series of Erdos-problem resolutions in this catalog.

Verification

Single-author arXiv preprint; not yet peer-reviewed.

Source

arXiv:2606.17901 - The Erdos-Hajnal High-Girth Subgraph Conjecture Holds in the Polynomial Chromatic-Sparsity Regime

The Erdos-Hajnal High-Girth Subgraph Conjecture

What was actually shown

What the AI did

Verification

Source

Discussion