Elsevier

Discrete Mathematics

Volume 195, Issues 1–3, 28 January 1999, Pages 251-254
Discrete Mathematics

Note
Packing and covering triangles in graphs

https://doi.org/10.1016/S0012-365X(98)00183-6Get rights and content
Under an Elsevier user license
open archive

Abstract

It is shown that if G is a graph such that the maximum size of a set of pairwise edge-disjoint triangles is v(G), then there is a set C of edges of G of size at most (3 − ε)v(G) such that E(T) ∩ C ≠ ∅ for every triangle T of G, where ε > 323. This is the first nontrivial bound known for a long-standing conjecture of Tuza.

Cited by (0)

The author was partially supported by NSERC.