Packing triangles in weighted graphs

DOI10.1137/100803869MaRDI QIDQ4979838zbMATH OpenOpenAlexFDO

Authors Guillaume Chapuy, Matt DeVos, Jessica McDonald, Bojan Mohar, Diego Scheide

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coveringpackingtriangles

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Tuza conjectured that for every graph $G$, the maximum size $u$ of a set of edge-disjoint triangles and minimum size $au$ of a set of edges meeting all triangles satisfy $auleq2u$. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich who proved that $auleq2u^{\ast }$ (where $u^{\ast }$ is the fractional version of $u$), and asked if this is tight. We prove that $auleq2u^{\ast }-frac1sqrt6sqrt{u}^{\ast }$ and show that this bound is essentially best possible.

Recommendations

• Covering triangles in edge-weighted graphs
• Packing and covering directed triangles asymptotically
• Packing and covering triangles in tripartite graphs
• On a conjecture of Tuza about packing and covering of triangles
• Sufficient conditions for Tuza's conjecture on packing and covering triangles

Cited in

(17)

• Triangle packings and 1-factors in oriented graphs
• Maximal flat antichains of minimum weight
• Packing and covering triangles in graphs
• Packing and covering triangles in tripartite graphs
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• Small edge sets meeting all triangles of a graph
• Packing and covering directed triangles asymptotically
• Triangle packing and covering in dense random graphs
• Packing and covering directed triangles
• Tuza's conjecture for graphs with maximum average degree less than 7
• Fractional \(K_{4}\)-covers
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Total dual integrality of triangle covering
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
• Monotonic decompositions of submodular set functions
• Covering triangles in edge-weighted graphs
• Packing and covering triangles in planar graphs

This page was built for publication: Packing triangles in weighted graphs

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