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 $\overline {G}$ ? 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 2 /12 +  o ( n 2 ). 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 $\overline {G}$ is at least n 2 /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