Sufficient conditions for Tuza's conjecture on packing and covering triangles

DOI10.1007/978-3-319-44543-4_21MaRDI QIDQ2819510zbMATH OpenOpenAlexFDO

Authors Zhuo Diao, Xiaodong Hu, Zhongzheng Tang, Xujin Chen

Publication date 29 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.01816

zbMATH Keywords

combinatorial algorithmslinear 3-uniform hypergraphstriangle covertriangle packing

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $u_t(G)$ and $a{u}_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 $a{u}_t(G)/u_t(G)le2$ 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 $2u_t(G)$ can be found in polynomial time if one of the following conditions is satisfied: (i) $u_t(G)/|mathscr{T}_G|gefrac13$, (ii) $u_t(G)/|E|gefrac14$, (iii) $|E|/|mathscr{T}_G|ge2$. Keywords: Triangle cover, Triangle packing, Linear 3-uniform hypergraphs, Combinatorial algorithms

Recommendations

• Covering triangles in edge-weighted graphs
• Packing and covering triangles in planar graphs
• On a conjecture of Tuza about packing and covering of triangles
• Triangle packing and covering in dense random graphs
• Packing and covering triangles in tripartite graphs

Cites work

• A conjecture on triangles of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• On a Class of Totally Unimodular Matrices
• On a conjecture of Tuza about packing and covering of triangles
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• Packing and covering triangles in graphs
• Packing and covering triangles in planar graphs
• Packing and covering triangles in tripartite graphs
• Packing triangles in weighted graphs
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Tuza's conjecture is asymptotically tight for dense graphs

Cited in

(14)

• Packing and covering triangles in tripartite graphs
• On a conjecture of Tuza about packing and covering of triangles
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Packing and covering directed triangles asymptotically
• Triangle packing and covering in dense random graphs
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• On the feedback number of 3-uniform linear extremal hypergraphs
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Packing triangles in weighted graphs
• A generalization of Tuza's conjecture
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• On Tuza's conjecture for triangulations and graphs with small treewidth
• On Tuza's conjecture for triangulations and graphs with small treewidth
• Covering triangles in edge-weighted graphs

This page was built for publication: Sufficient conditions for Tuza's conjecture on packing and covering triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819510)