K₃ polynomial anticomplete pair property
Open case H = K3 for Conjecture 1.4 · arXiv:1810.00058
Status open medium confidence
The $K_3$ (triangle) case of Conjecture 1.4 from arXiv:1810.00058 remains open as of May 2026. The paper's main result covers all almost-bipartite $H$, but since $K_3$ contains a triangle it lies outside this class. Substantial follow-up work by Buci\'c, Fox, Nguyen, Pham, Scott, and Seymour has made progress on related conjectures in the same paper (the polynomial R\"odl / Fox-Sudakov conjecture, Conjecture 1.7) and on the Erd\H{o}s-Hajnal programme more broadly, but no paper specifically resolving the $K_3$ case of Conjecture 1.4 was found.
Reviewer notes. The internal references from the curated corpus appear to concern Conjecture 1.7 (polynomial R\"odl / Fox-Sudakov conjecture) from the same paper, not Conjecture 1.4 about polynomial-sized anticomplete pairs. The equivalence result of Buci\'c-Fox-Pham (2403.08303) and the Erd\H{o}s-Hajnal loglog improvement (2301.10147) are part of the same broad programme but do not directly settle Conjecture 1.4 for K_3. The K_3 case of Conjecture 1.4 is noted as still open in the 2020 paper and no follow-up resolving it was found in the indexed literature.
Context
The paper's main result establishes Conjecture 1.4 for all almost-bipartite graphs $H$; almost-bipartite graphs are triangle-free, so $K_3$ is the simplest graph not covered. This gap is noted both in the abstract and in the body of the paper.
Notes. PDF source; stated informally as 'it remains open whether H = K_3 satisfies 1.4'
Source paper
Sparse graphs with no polynomial-sized anticomplete pairs
Maria Chudnovsky, Jacob Fox, Alex Scott, Paul Seymour, Sophie Spirkl · 2020-12-07
https://arxiv.org/abs/1810.00058
PDF source