2010/09/02 by Raphael Yuster, Yuster, Raphael
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1009.0353
arxiv created 2010/09/02 · openalex publication_date 2010/09/02 · arxiv updated 2010/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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β2) pairwise edge-disjoint triangles where β 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.