Covering the edges of a graph with triangles (Q6635092)

Motivated by a question of \textit{P. Erdős} et al. [ibid. 150, No. 1--3, 89--101 (1996; Zbl 0857.05077)], the authors study the relationship between the following graph invariants. Let~\(G\) be an undirected graph.\N\begin{itemize}\N\item \(\rho_{\Delta}(G)\) is the minimum cardinality of a set consisting of edges and triangles that together cover~\(E(G)\);\N\item \(\alpha_1(G)\) is the maximum cardinality of an edge set that contains at most one edge from each triangle in~\(G\), also called the triangle-independence number of~\(G\);\N\item \(\nu_{\Delta}(G)\) is the maximum number of pairwise edge-disjoint triangles in~\(G\).\N\end{itemize}\NAmong other results, they prove that for every graph~\(G\) with~\(m\) edges,\N\[\N\rho_\Delta(G) \le \left\lfloor\frac{1}{2}\left(m+\alpha_1(G)-\nu_\Delta(G)\right)\right\rfloor.\N\]\NThe above upper bound for \(\rho_\Delta(G)\) is tight as the authors show that, for any positive integer \(n\), there exists an \(n\)-vertex graph \(G\) with the equality. The authors also prove the following Nordhaus-Gaddum-type inequalities for~\(\alpha_1\) and~\(\rho_{\Delta}\): for any \(n\)-vertex graph~\(G\),\N\[\N\alpha_1(G)+\alpha_1(\overline{G})\le \frac{n^2}{4}+O\left(\frac{n^2}{\ln n}\right),\N\]\Nholds as \(n\to\infty\), and\N\[\N\rho_{\Delta}(G)+\rho_{\Delta}(\overline{G})\le\frac{n^2}{3}+o(n^2).\N\]\NBoth upper bounds are asymptotically tight.