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.
