Sharp asymptotics for triangle independence and covering numbers

Abstract

For a graph $G$, let $\alpha_1(G)$ be the maximum size of an edge set containing at most one edge from every triangle, and let $\tau_1(G)$ be the minimum size of an edge set meeting every triangle. Erd\H{o}s, Gallai, and Tuza proved that $\alpha_1(G)+\tau_1(G)=\Omega(m^{2/3})$ for every $m$-edge graph and asked for the optimal asymptotic constant. We prove $$\lim_{m\to\infty} \min_{G,\,|E(G)|=m} \frac{\alpha_1(G) + \tau_1(G)}{m^{2/3}} = \frac{3}{2},$$ thereby establishing that the sharp constant is $3/2$ and solving the problem.