Triangle-packing vs triangle edge-transversal.
Status partial high confidence
Tuza's conjecture ($\tau(G)\leq 2\nu(G)$) remains open for general graphs. Since the OPG posting, the conjecture has been confirmed for several important graph classes (treewidth $\leq 6$, threshold graphs, random graphs, planar triangulations with the sharper bound $\tau(G)\leq \frac{3}{2}\nu(G)$), and Baron–Kahn showed the factor 2 is asymptotically tight for dense graphs. The best known general bound is still Haxell's $(3-\frac{3}{23})\nu(G)$ from 1999.
Cited literature (5)
-
Constructs arbitrarily large dense graphs where $\tau(G)/(\nu(G))\to 2$, showing the bound in Tuza's conjecture is asymptotically tight and disproving a conjecture by Yuster that it could be improved.
-
Proves that for every $k\geq 2$ there exists a multiset $F\subseteq E(G)$ with $|F|\leq 2k\nu(G)$ such that every triangle meets $F$ at least $k$ times, strengthening Krivelevich's fractional results.
-
Verifies Tuza's conjecture for all graphs with treewidth at most 6, and proves the sharper bound $\tau(G)\leq\frac{3}{2}\nu(G)$ for planar triangulations other than $K_4$.
-
partial Closing the Random Graph Gap in Tuza's Conjecture Through the Online Triangle Packing Process (2020)
Proves that Tuza's conjecture holds with high probability in the Erdős–Rényi random graph $G(n,m)$ for all ranges of $m$, closing a previously open gap.
-
Confirms Tuza's conjecture for threshold graphs (simultaneously split graphs and cographs) and for co-chain graphs satisfying certain divisibility conditions.
Reviewer notes. The SIAM journal page for Bennett–Cushman–Dudek returned HTTP 403; the DOI 10.1137/20M1351771 is taken from the URL that appeared in search results, while the paper details were confirmed via the arXiv abstract. The 2024 arXiv:2406.06501 paper (Parker) concerns the Aharoni–Zerbib generalization to k-uniform hypergraphs, not Tuza's original conjecture, and was therefore excluded from since_posted. The best general bound remains Haxell's $(3-3/23)\nu(G)$ from 1999; no improvement to the general case was found in post-2013 literature.
Discussion
This conjecture may be rephrased in terms of packing and edge-transversal. A triangle packing is a set of pairwise edge-disjoint triangles. A triangle edge-tranversal is a set of edges meeting all triangles. Denote the maximum size of a triangle packing in $ G $ by $ \nu(G) $ and the minimum size of a triangle edge-transversal of $ G $ by $ \tau(G) $ . Clearly $ \nu(G) \leq \tau(G) $ . The conjecture translates in $ \tau(G)\leq 2\nu(G) $ . This conjecture, if true, is best possible as can be seen by taking, say $ G=K_4 $ or $ G=K_5 $ . Trivially, $ \tau(G)\leq 3\nu(G) $ , since the set of edges of a maximum triangle packing is a triangle edge-transversal. Haxell [H] proved that $ \tau(G) \leq (3-\frac{3}{23})\nu(G) $ edges whose deletion destroys every triangle. As usual, one can define fractional packing and fractional transversal. Let $ {\cal T} $ be the set of triangles of $ G $ . A fractional triangle packing is a function $ f:{\cal T}\rightarrow \mathbb{R}^+ $ such that $ \sum_{T\ni e} \leq 1 $ for every edge $ e $ . A fractional triangle edge-transversal is a function $ g:E\rightarrow \mathbb{R}^+ $ such that $ \sum_{e\in T} g(e)\geq 1 $ for every triangle $ T\in {\cal T} $ . We denote by $ \nu^*(G) $ the maximum of $ \sum_{T\in {\cal T}} f(T) $ over all fractional triangle packing and by $ \tau^*(G) $ the minimum of $ \sum_{e\in E(G)} g(e) $ over all fractional edge-transversals. By duality of linear programming $ \tau^*(G) = \nu^*(G) $ . Krivelevich [K] proved two fractional versions of the conjecture: $ \tau(G) \leq 2\nu^*(G) $ and $ \tau^*(G)\leq 2\nu(G) $ .
Bibliography
-
[H]P.Haxell, Packing and covering triangles in graphs, Discrete Mathematics 195 (1999), no. 1–3, 251–254. -
[K]M. Krivelevich, On a conjecture of Tuza about packing and covering of triangles Discrete Mathematics 142 (1995), 281-286. -
★
[T]Z. Tuza, A conjecture on triangles of graphs. Graphs Combin. 6 (1990), 373-380.