We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Large triangle packings and Tuza's conjecture in sparse random graphs.
- Authors
Bennett, Patrick; Dudek, Andrzej; Zerbib, Shira
- 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 2v(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.2403n3/2 or m ⩾ 2.1243n3/2. This is done by analysing a greedy algorithm for finding large triangle packings in random graphs.
- Subjects
SPARSE graphs; RANDOM graphs; TRIANGLES; INTERSECTION graph theory; LOGICAL prediction; GREEDY algorithms
- Publication
Combinatorics, Probability & Computing, 2020, Vol 29, Issue 5, p757
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548320000115