Polynomial Nikiforov universality for graphs

Conjecture 1.8 · arXiv:2307.06455

arXiv Conjecture high confidence— first stated 2026-04-18

Authors: Tung Nguyen, Alex Scott, Paul Seymour

Status open high confidence

Conjecture 1.8 (the 'polynomial Nikiforov' conjecture) asserts that every graph H is viral, i.e., satisfies a polynomial-bound version of Nikiforov's theorem via ε-restricted subsets. Bucić, Fox, and Pham (arXiv:2403.08303, 2024) proved that the Erdős-Hajnal property is equivalent to being viral, establishing that Conjecture 1.8 is in turn equivalent to the full Erdős-Hajnal conjecture; since the latter remains open, so does Conjecture 1.8. No direct proof or counterexample for Conjecture 1.8 was found in the 2025–2026 literature.

Cited literature (1)

reduction Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures (2024)

Matija Bucić, Jacob Fox, Huy Tuan Pham · arXiv preprint · arXiv:2403.08303

Proves that having the Erdős-Hajnal property is equivalent to being viral (i.e., satisfying Conjecture 1.8), thereby reducing the conjecture to the full Erdős-Hajnal conjecture.

Reviewer notes. Conjecture 1.8 is equivalent to the full Erdős-Hajnal conjecture via the Bucić-Fox-Pham equivalence (arXiv:2403.08303). The source paper was first posted in July 2023; the 2026-04-18 date is the journal publication, which already cites Bucić-Fox-Pham as reference [4]. No further resolution found in the literature.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every graph $H$, there exists $d>0$ such that for every $\varepsilon\in(0,\frac{1}{2})$ and every graph $G$ with $\mathrm{ind}_{H}(G)\leq(\varepsilon^{d}\lvert G\rvert)^{\lvert H\rvert}$, there is an $\varepsilon$-restricted subset of $V(G)$ with size at least $\varepsilon^{d}\lvert G\rvert$.

Context

This 'polynomial Nikiforov' statement, introduced without external attribution, unifies Theorem 1.6 and Conjecture 1.7. A graph $H$ satisfying it is called viral; Bucić, Fox, and Pham [4] proved that having the Erdős-Hajnal property is equivalent to being viral.

Source paper

Induced subgraph density. IV. New graphs with the Erdős-Hajnal property
Tung Nguyen, Alex Scott, Paul Seymour · 2026-04-18
https://arxiv.org/abs/2307.06455