PreprintarXiv licencearXiv
Tuza's Conjecture under an Edge-Count Condition
Abstract
For a graph G, let ν(G) denote the maximum number of pairwise edge-disjoint triangles and let τ(G) denote the minimum number of edges meeting every triangle. Tuza's conjecture asserts that τ(G)≤ 2ν(G) for every graph G. We first note that Tuza's conjecture is equivalent to the following statement: for every fixed c≥ 0, if G is a sufficiently large n-vertex graph with e(G)≥ n2/4−cn, then τ(G)≤ 2ν(G). In this paper, we prove this statement for every c<2.
Related
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- A Tight Fractional Version of Generalized Tuza's Conjecture
- Tuza's Ryser-conjecture claim for four-partite hypergraphs with matching number two
- A Bound Below 2.8 for Tuza's Conjecture
- Gaussian Vertex-Face Balance in Random Convex Polyhedra with Fixed Edge Count
BibTeX
@misc{liu2026tuzas,
title = {{Tuza's Conjecture under an Edge-Count Condition}},
author = {Zhen Liu and Qinghou Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15539},
eprint = {2610.15539},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15539},
}
RIS
TY - UNPB
TI - Tuza's Conjecture under an Edge-Count Condition
AU - Zhen Liu
AU - Qinghou Zeng
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15539
UR - https://arxiv.org/abs/2610.15539
AB - For a graph G, let ν(G) denote the maximum number of pairwise edge-disjoint triangles and let τ(G) denote the minimum number of edges meeting every triangle. Tuza's conjecture asserts that τ(G)≤ 2ν(G) for every graph G. We first note that Tuza's conjecture is equivalent to the following statement: for every fixed c≥ 0, if G is a sufficiently large n-vertex graph with e(G)≥ n^2/4−cn, then τ(G)≤ 2ν(G). In this paper, we prove this statement for every c<2.
ER -