Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
share
Given a simple graph G=(V,E), a subset of E is called a triangle cover if it intersects each triangle of G. Let ν_t(G) and τ_t(G) denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza conjectured in 1981 that τ_t(G)/ν_t(G)<2 holds for every graph G. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza's conjecture on covering and packing triangles. More precisely, suppose that the set T_G of triangles covers all edges in G. We show that a triangle cover of G with cardinality at most 2ν_t(G) can be found in polynomial time if one of the following conditions is satisfied: (i) ν_t(G)/| T_G|>1/3, (ii) ν_t(G)/|E|>1/4, (iii) |E|/| T_G|>2. Keywords: Triangle cover, Triangle packing, Linear 3-uniform hypergraphs, Combinatorial algorithms
READ FULL TEXT