Packing and covering triangles in tripartite graphs (Q1385295)

This paper concerns an unresolved conjecture of \textit{Zs. Tuza} [Proc. Colloq. Math. Soc. János Bolyai 37 (1984), p. 808]. A set of triangles in a graph \(G\) is called independent if the triangles are pairwise edge-disjoint. Denote by \(\nu (G)\) the maximum cardinality of an independent set of triangles in \(G\). A set \(C\) of edges of \(G\) is called a transversal for \(G\) if every triangle of \(G\) contains at least one edge in \(C\). Denote by \(\tau (G)\) the minimum cardinality of a transversal for \(G\). Tuza conjectured that \(\tau (G) \leq 2 \nu (G)\) for every graph \(G\). The authors prove that for every tripartite graph \(G\) one has \(\tau(G) \leq (2-\varepsilon) \nu (G)\) where \(\varepsilon > 0.044\).