Tuza’s Conjecture asserts that the minimum number τ′Δ(G) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number ν′Δ(G) of edge-disjoint triangles of G. The complete graphs K4 and K5 show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for K4 -free graphs. In this paper, we consider several subclasses of K4 -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 τ′Δ(G) and ν′Δ(G) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide θ -bounding functions for classes related to triangle graphs. In particular, we obtain optimal θ -bounding functions for the classes Free(K5, claw, diamond ) and Free(P5, diamond ,K2,3) and a χ -bounding function for the class ( banner, odd-hole ,K1,4¯¯¯¯¯¯¯¯¯) .
|Journal||Graphs and Combinatorics|
|Early online date||19 May 2018|
|Publication status||Published - 01 Jul 2018|
- Triangle graphs
- Triangle packing and transversal