For a graph G, let alpha_1(G) be the maximum cardinality of an edge set F⊆ E(G) such that |F cap E(T)|≤ 1 for every triangle T of G, and let tau_1(G) be the minimum cardinality of an edge set F⊆ E(G) such that F cap E(T)≠varnothing for every triangle T of G. Determine the optimal asymptotic constant governing alpha_1(G)+tau_1(G) over graphs with m edges; equivalently, determine the value and existence of lim_m→∞min_|E(G)|=mfracalpha_1(G)+tau_1(G)m^2/3.

Erdős–Gallai–Tuza triangle independence-covering problem

For a graph $G$ , let $\alpha_1(G)$ be the maximum cardinality of an edge set $F\subseteq E(G)$ such that $|F\cap E(T)|\le 1$ for every triangle $T$ of $G$ , and let $\tau_1(G)$ be the minimum cardinality of an edge set $F\subseteq E(G)$ such that $F\cap E(T)\ne\varnothing$ for every triangle $T$ of $G$ . Determine the optimal asymptotic constant governing $\alpha_1(G)+\tau_1(G)$ over graphs with $m$ edges; equivalently, determine the value and existence of $\lim_{m\to\infty}\min_{|E(G)|=m}\frac{\alpha_1(G)+\tau_1(G)}{m^{2/3}}$ .

Progress summary

Solved

A new unrefereed preprint claims to give the exact long-term constant, but the result has not yet been independently checked.

Erdős, Gallai, and Tuza asked for the optimal asymptotic constant governing triangle independence and covering numbers in an $m$ -edge graph. Earlier work concerned a related $n$ -vertex inequality rather than this sharp-constant problem.

Known results

Puleo (2015) reduced the related unrestricted $n$ -vertex conjecture to triangular graphs by showing that a vertex-minimal counterexample has minimum degree greater than $n/2$ .
Earlier work established $\alpha_1(G)+\tau_1(G)=\Omega(m^{2/3})$ and studied the distinct bound $\alpha_1(G)+\tau_1(G)\leq 5n^2/16$ .

August 2026 claimed exact constant

Liu and Zeng’s arXiv preprint claims $$\lim_{m\to\infty}\min_{|E(G)|=m}\frac{\alpha_1(G)+\tau_1(G)}{m^{2/3}}=\frac{3}{2}. $\nIt gives matching bounds up to order$ m^{1/3}$ and an extremal construction, but the result is unrefereed and no independent verification or objection report was found.

Current status (as of August 2026): the sharp constant $3/2$ is claimed in a new preprint, but its correctness has not yet been independently verified.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Sharp asymptotics for triangle independence and covering numbers — arXiv — Zhen Liu, Qinghou Zeng

extremal-graph-theory

2 days ago