Packing triangles in weighted graphs

Tuza conjectured that for every graph $G$, the maximum size $ν$ of a set of edge-disjoint triangles and minimum size $τ$ of a set of edges meeting all triangles satisfy $τ\leq 2ν$. 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 $τ\leq 2ν^*$ (where $ν^*$ is the fractional version of $ν$), and asked if this is tight. We prove that $τ\leq 2ν^*-\frac{1}{\sqrt{6}}\sqrt{ν^*}$ and show that this bound is essentially best possible.

No reviews yet.

No comments yet.