Large triangle packings and Tuza's conjecture in sparse random graphs. (22nd September 2020)

• Record Type: Journal Article
• Authors: Bennett, Patrick; Dudek, Andrzej; Zerbib, Shira
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 5(2020)
• Page Start: 757
• Page End: 779
• Publication Date: 2020-09-22
• Subjects: 05B40, -- 05C80, -- 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000115
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: The triangle packing number v ( 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 v ( G ) edges intersecting every triangle in G . We show that Tuza's conjecture holds in the random graph G = G ( n, m ), when m ⩽ 0.2403 n 3/2 or m ⩾ 2.1243 n 3/2 . This is done by analysing a greedy algorithm for finding large triangle packings in random graphs.