标题： 稠密图具有大的三角形覆盖则具有大的三角形包装 显示英文标题

标题： Dense graphs with a large triangle cover have a large triangle packing

摘要： 众所周知，具有$m$条边的图可以通过移除（略少于）$m/2$条边使其不含三角形。 另一方面，有许多图类在使它们不含三角形方面是困难的，即为了消除所有三角形，有必要移除大约$m/2$条边。 证明了那些难以变为不含三角形的稠密图，具有大量两两边不相交的三角形。 特别是，它们拥有超过$m(1/4+c\beta^2)$个两两边不相交的三角形，其中$\beta$是图的密度，$c$是一个绝对常数。 这改进了之前的一个$m(1/4-o(1))$界，该界来源于对稠密图中 Tuza 猜想渐近成立性的推论。 人们猜想这样的图具有渐近最优的三角形包装，大小为$m(1/3-o(1))$。 该结果被扩展到更大的团和奇数环。 显示英文摘要

摘要： It is well known that a graph with $m$ edges can be made triangle-free by removing (slightly less than) $m/2$ edges. On the other hand, there are many classes of graphs which are hard to make triangle-free in the sense that it is necessary to remove roughly $m/2$ edges in order to eliminate all triangles. It is proved that dense graphs that are hard to make triangle-free, have a large packing of pairwise edge-disjoint triangles. In particular, they have more than $m(1/4+c\beta^2)$ pairwise edge-disjoint triangles where $\beta$ is the density of the graph and $c$ is an absolute constant. This improves upon a previous $m(1/4-o(1))$ bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. It is conjectured that such graphs have an asymptotically optimal triangle packing of size $m(1/3-o(1))$. The result is extended to larger cliques and odd cycles.