Abstract
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¯¯¯¯¯¯¯¯¯) .
Original language | English |
---|---|
Pages (from-to) | 647-668 |
Journal | Graphs and Combinatorics |
Volume | 34 |
Issue number | 4 |
Early online date | 19 May 2018 |
DOIs | |
Publication status | Published - 01 Jul 2018 |
Keywords
- Triangle graphs
- Triangle packing and transversal
- χ-Bounded