






















A celebrated conjecture of Zs. Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: \[ \mbox{for any $p=p(n)$, $\mathbb P(\mbox{$G_{n,p}$ satisfies Tuza's Conjecture})\rightarrow 1 $ (as $n\rightarrow\infty$).} \]
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。