Large triangle packings and Tuza's conjecture in sparse random graphs

The triangle packing number $ν(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2ν(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.

No reviews yet.

No comments yet.