Packing triangles in a graph and its complement

How few edge‐disjoint triangles can there be in a graph G on n vertices and in its complement ? This question was posed by P. Erd?s, who noticed that if G is a disjoint union of two complete graphs of order n/2 then this number is n²/12 + o(n²). Erd?s conjectured that any other graph with n vertices together with its complement should also contain at least that many edge‐disjoint triangles. In this paper, we show how to use a fractional relaxation of the above problem to prove that for every graph G of order n, the total number of edge‐disjoint triangles contained in G and is at least n²/13 for all sufficiently large n. This bound improves some earlier results. We discuss a few related questions as well. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 203–216, 2004