PreprintCC BY 4.0arXiv
A Bound Below 2.8 for Tuza's Conjecture
Abstract
Let ν(G) be the maximum number of edge-disjoint triangles in a graph G and τ(G) the minimum number of edges meeting every triangle. Tuza conjectured that τ(G)≤ 2ν(G). We prove that τ(G)≤ (165/59)ν(G). The constant 165/59≈ 2.797 improves the bound 66/23≈ 2.870 that Haxell proved in 1999. The key observation is that, for a suitable red-blue coloring, the families left over in Haxell's construction contain every triangle with exactly one red edge. Such a family ℱ admits an exchange that forces certain red edges to lie in a single triangle once the blue edges of a maximum packing are deleted, which gives τ(ℱ)≤ (8/3)ν(ℱ).
Related
BibTeX
@misc{wang2026bound,
title = {{A Bound Below 2.8 for Tuza's Conjecture}},
author = {Sichen Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13831},
eprint = {2609.13831},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13831},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Bound Below 2.8 for Tuza's Conjecture
AU - Sichen Wang
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13831
UR - https://arxiv.org/abs/2609.13831
AB - Let ν(G) be the maximum number of edge-disjoint triangles in a graph G and τ(G) the minimum number of edges meeting every triangle. Tuza conjectured that τ(G)≤ 2ν(G). We prove that τ(G)≤ (165/59)ν(G). The constant 165/59≈ 2.797 improves the bound 66/23≈ 2.870 that Haxell proved in 1999. The key observation is that, for a suitable red-blue coloring, the families left over in Haxell's construction contain every triangle with exactly one red edge. Such a family ℱ admits an exchange that forces certain red edges to lie in a single triangle once the blue edges of a maximum packing are deleted, which gives τ(ℱ)≤ (8/3)ν(ℱ).
ER -