Tuza's Conjecture is Asymptotically Tight for Dense Graphs
| Autor: | Baron, Jacob D., Kahn, Jeff |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | Combinatorics, Probability and Computing (2016) 25, 645-67 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1017/S0963548316000067 |
| Popis: | An old conjecture of Zs. Tuza says that for any graph $G$, the ratio of the minimum size, $\tau_3(G)$, of a set of edges meeting all triangles to the maximum size, $\nu_3(G)$, of an edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive $\alpha$ there are arbitrarily large graphs $G$ of positive density satisfying $\tau_3(G)>(1-o(1))|G|/2$ and $\nu_3(G)<(1+\alpha)|G|/4$. Comment: Changes in version 2: fixed typos; clarified introduction slightly; clarified discussion of "gain/loss at an edge" at the bottom of p. 13. Results unchanged. 22 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|