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ő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 $$\underset{m\to \infty }{\lim }\underset{G,|E(G)|=m}{\min }\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.