An improved upper bound for Tuza's conjecture via 2-colorable triangle families

Abstract

Tuza's conjecture states that for any graph $G$, the minimum size of a triangle transversal $\tau(G)$ is at most twice the maximum size of a set of edge-disjoint triangles $\nu(G)$. In this note, we prove $\tau(G) \leq \frac{63}{22}\nu(G)$, improving the previous bound $\tau(G) \leq \frac{66}{23}\nu(G)$ established by Haxell in 1999. The key observation is that for a"2-colorable"family of triangles $\mathcal{F}$, where each triangle has two blue edges and one red edge, we can obtain $\tau(\mathcal{F})\leq (1+\sqrt{3})\nu(\mathcal{F})$.