Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles

2016/05/06 by Chen, Xujin, Diao, Zhuo, Hu, Xiaodong +1
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Graphics (cs.GR)

paper · doi:10.48550/arxiv.1605.01816

Abstract

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 \mathscr 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)/|\mathscr T_G|≥\frac13, (ii) ν_t(G)/|E|≥\frac14, (iii) |E|/|\mathscr T_G|≥2. Keywords: Triangle cover, Triangle packing, Linear 3-uniform hypergraphs, Combinatorial algorithms

Related

• Closing the Random Graph Gap in Tuza's Conjecture Through the Online\n Triangle Packing Process
• Multi-transversals for Triangles and the Tuza's Conjecture
• A generalization of Tuza's conjecture
• Large triangle packings and Tuza's conjecture in sparse random graphs
• Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture