Bollobás–Erdős–Tuza conjecture

For every constant $c>0$ , there exists a function $f_c(n)=o(n)$ such that every graph $G$ on $n$ vertices with independence number $\alpha(G)\ge cn$ satisfies $h(G)\le f_c(n)$ , where $h(G)$ is the minimum cardinality of a vertex set meeting every maximum independent set of $G$ . Equivalently, for every $c,\varepsilon>0$ , there exists $n_0$ such that every graph $G$ with $|V(G)|=n\ge n_0$ and $\alpha(G)\ge cn$ has $h(G)\le\varepsilon n$ .

Progress summary

Partially solved

The conjecture remains open, but a new preprint reduces it to narrower graph families and proves several strong special cases.

Proposed by Bollobás, Erdős, and Tuza in the early 1990s, the conjecture predicts a sublinear set meeting every maximum independent set whenever the independence number is linear in the number of vertices.

Known results

Alon proved bounds for regular graphs with independence ratio greater than $1/4+\varepsilon$ .
Cheng and Xu proved the conjecture for several classes, including even-hole-free, disk, and circle graphs.
Graphs with no induced $K_{s,t}$ , for fixed $t\ge s$ , satisfy the conjecture (2024).
Graphs with no induced matching of size $t$ satisfy a quantitative bound, including the $P_5$ -free case (2024).

August 2026 reductions

Bai, Hanzhi, Chang, Yufei, Yan, and Jin claim equivalence with the restriction to regular graphs of any fixed positive linear degree and, within hereditary classes, with graphs having fixed positive linear vertex-connectivity. They also give sharp bounds in several cases, including $h(G)\le 3$ when $\kappa(G)>n/2$ ; these are reductions and special cases, not a proof of the unrestricted conjecture.

Current status (as of August 2026): The unrestricted conjecture remains open; substantial restricted-case results and new reductions to regular and highly connected graphs are available.

Sources

arxiv.org

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Regular-graph formulation of the Bollobás–Erdős–Tuza conjecture
For every fixed $\rho>0$ and every $c>0$ , there exists a function $f_{c,\rho}(n)=o(n)$ such that every $\lfloor\rho n\rfloor$ -regular graph $G$ on $n$ vertices with $\alpha(G)\ge cn$ satisfies $h(G)\le f_{c,\rho}(n)$ . The unrestricted conjecture is equivalent to this restriction for every fixed positive linear degree.
source: Bai, Chang, Yan, and Jin, “Hitting Maximum Independent Sets in Dense and Highly Connected Graphs”