An improved upper bound for Tuza's conjecture via 2-colorable triangle families
Tuza's conjecture states that for any graph $G$, the minimum size of a triangle transversal $τ(G)$ is at most twice the maximum size of a set of edge-disjoint triangles $ν(G)$. In this note, we prove $τ(G) \leq \frac{63}{22}ν(G)$, improving the previous bound $τ(G) \leq \frac{66}{23}ν(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 $τ(\mathcal{F})\leq (1+\sqrt{3})ν(\mathcal{F})$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.23010
curl -X POST /api/v1/records/arxiv/2608.23010/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.23010/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'