Name
Abstract | ||
|---|---|---|
The triangle packing number nu(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 nu(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.2403n(3/2) or m >= 2.1243n(3/2). This is done by analysing a greedy algorithm for finding large triangle packings in random graphs. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1017/S0963548320000115 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 29 | 5 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P BENNETT | 1 | 15 | 5.42 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Shira Zerbib | 3 | 3 | 3.47 |