Triangle Packings and Transversals of Some -Free Graphs

摘要

Tuza's Conjecture asserts that the minimum number tau(Delta)'(G) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number nu(Delta)'(G) of edge-disjoint triangles of G. The complete graphs K-4 and K-5 show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for K-4-free graphs. In this paper, we consider several subclasses of K-4-free graphs. We show that the constant 2 can be improved for them and we try to provide the optimal one. The classes we consider are of two kinds: graphs with edges in few triangles and graphs obtained by forbidding certain odd-wheels. We translate an approximate min-max relation for tau(Delta)'(G) and nu(Delta)'(G) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide theta-bounding functions for classes related to triangle graphs. In particular, we obtain optimal.-bounding functions for the classes Free(K-5, claw, diamond) and Free(P-5, diamond, K-2,K-3) and a chi-bounding function for the class (banner, odd-hole, (K-1,K-4) over bar).