The factor-two relation between triangle deletion and packing
For a finite simple graph $G$, let $\nu(G)$ be the largest number of pairwise edge-disjoint triangles in $G$, which may share vertices, and let $\tau(G)$ be the least number of edges of $G$ meeting every triangle of $G$; both are $0$ when $G$ has no triangle. The complete graph $K_4$ has $\nu = 1$ and $\tau = 2$. Tuza proved the inequality below for planar graphs, Krivelevich for graphs containing no subdivision of $K_{3,3}$, and Puleo for graphs of maximum average degree less than $7$. Krivelevich also proved the fractional versions $\tau \le 2\tau^*$ and $\nu^* \le 2\nu$, where $\tau^*$ and $\nu^*$ are the fractional covering and packing numbers. Haxell proved $\tau(G) \le \tfrac{66}{23}\nu(G)$ for every $G$, and Kahn and Park proved that for every $p = p(n)$ the random graph $G(n,p)$ satisfies the inequality below with probability tending to one.
Problem. Is $\tau(G) \le 2\nu(G)$ for every finite simple graph $G$?
Source: Tuza (1981; proceedings published 1984); see Tuza (1990) and Krivelevich (1995), Conjecture 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, triangle covers, triangle packings, Tuza's conjecture
References
@incollection{tuza1984,
author = {Tuza, Zsolt},
title = {Conjecture},
booktitle = {Finite and Infinite Sets ({E}ger, 1981)},
editor = {Hajnal, A. and Lov{\'a}sz, L. and S{\'o}s, V. T.},
series = {Colloq. Math. Soc. J{\'a}nos Bolyai},
volume = {37},
publisher = {North-Holland},
address = {Amsterdam},
year = {1984},
pages = {888},
}
@article{tuza1990,
author = {Tuza, Zsolt},
title = {A conjecture on triangles of graphs},
journal = {Graphs Combin.},
volume = {6},
number = {4},
year = {1990},
pages = {373--380},
doi = {10.1007/BF01787705},
}
@article{krivelevich1995,
author = {Krivelevich, Michael},
title = {On a conjecture of {T}uza about packing and covering of triangles},
journal = {Discrete Math.},
volume = {142},
number = {1-3},
year = {1995},
pages = {281--286},
doi = {10.1016/0012-365X(93)00228-W},
}
@article{puleo2015,
author = {Puleo, Gregory J.},
title = {Tuza's conjecture for graphs with maximum average degree less than 7},
journal = {European J. Combin.},
volume = {49},
year = {2015},
pages = {134--152},
doi = {10.1016/j.ejc.2015.03.006},
}
@article{haxell1999,
author = {Haxell, P. E.},
title = {Packing and covering triangles in graphs},
journal = {Discrete Math.},
volume = {195},
number = {1-3},
year = {1999},
pages = {251--254},
doi = {10.1016/S0012-365X(98)00183-6},
}
@article{kahn2022,
author = {Kahn, Jeff and Park, Jinyoung},
title = {Tuza's conjecture for random graphs},
journal = {Random Structures Algorithms},
volume = {61},
number = {2},
year = {2022},
pages = {235--249},
doi = {10.1002/rsa.21057},
eprint = {2007.04351},
archivePrefix = {arXiv},
}
@misc{aim-tuza-triangle-packing-covering,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The factor-two relation between triangle deletion and packing}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/335-tuza-triangle-packing-covering.md},
note = {Entry 335 at commit a153f46, 2026-10-13},
}
Resolution claims
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)\le 2ν(G)$ for every graph $G$. We first note that Tuza's conjecture is equivalent to the following statement: for every fixed $c\ge 0$, if $G$ is a sufficiently large $n$-vertex …
For a finite simple graph $G$, let $ν(G)$ be the maximum number of pairwise edge disjoint triangles and $τ(G)$ the minimum number of edges meeting every triangle. Tuza conjectured in 1981 that every such $G$ satisfies $τ(G) \le 2 ν(G).$ We prove the conjecture for the class of graphs with $Δ\le10.$
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-23 | Open → Partially resolved | The registry's curators | Tuza's Conjecture for Graphs of Maximum Degree at Most 10 v1 recorded from arXiv:2610.15269v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00397, "The factor-two relation between triangle deletion and packing", clopen.solutions.