Tuza's Conjecture is Asymptotically Tight for Dense Graphs
Tuza's Conjecture is Asymptotically Tight for Dense Graphs
复制标题
DOI：
10.1017/s0963548316000067
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Jacob D. Baron;J. Kahn
中科院分区：
文献类型：
--
作者：
Jacob D. Baron;J. Kahn
Z. Tuza 的一个古老猜想说，对于任何图 G，满足所有三角形的一组边的最小尺寸 τ3(G) 与边不相交三角形堆积的最大尺寸 ν3(G) 的比率至多为 2。这里，反驳 R. Yuster 的猜想，我们证明对于任何固定的正 α，存在满足正密度的任意大图 G τ3(G) > (1 − o(1))|G|/2 且 ν3(G) < (1 + α)|G|/4。
An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν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 α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4.