Fav Problem: A 30-year-old conjecture of Zsolt Tuza

Okay, so this one isn't too deeply attached to TCS, but anyways.
Suppose G is a (finite) graph in which we can choose k edge-disjoint triangles but not more.
We want to make the graph triangle-free by removing edges, as few as possible. How many edges suffice?
Trivial observation #1: we have to remove at least k edges -- one from each triangle from a k-element edge-disjoint set of triangles.
Trivial observation #2: 3k edges surely suffice -- fix a maximal edge-disjoint set of triangles and remove all of their edges. (No triangle can remain intact, otherwise the set could not be maximal).
Now K4 is an example for a lower bound of 2k: from K4 we can choose at most one edge-disjoint triangle and we have to remove two edges to eliminate all triangles. (A disjoint sum of k K4s shows an example where k goes to infinity.)
The conjecture states that removing 2k edges always suffices.

Some progress on that: the conjecture holds (among other classes) for...

• planar graphs, Tuza 1985
• tripartite graphs, Haxell 1993
• K3,3-subdivision-free graphs, Krivelevich 1995
• graphs with maximum averagre degree at most 7, Puleo 2013.

I'm interested in the (correctness of the) last result, see here: http://arxiv-web3.library.cornell.edu/abs/1308.2211

anyone else? :-)