Sharp bounds for decomposing graphs into edges and triangles

In 1966 Erdos, Goodman and Posa showed that the edges of an n-vertex graph can be decomposed into at most n²/4 cliques. Moreover, they proved that such a decomposition may consist of edges and triangles only. About 15 years later, Gyori and Kostochka and independently Chung strengthened this result in order to answer a question of Katona and Tarjan by showing that the minimum sum of the orders of cliques in such edge-decompositions can be at most n²/2.

Motivated by the stronger version of the theorem of Erdos, Goodman and Posa, Gyori and Tuza asked whether one may consider only edges and triangles for the latter result as well. Specifically, they conjectured that the edge-set of every n-vertex graph can be decomposed into m edges and t triangles so that 2m+3t ≤ n²/2 + O(1). Recently, Kral, Lidicky, Martins and Pehova proved their conjecture asymptotically, i.e., found an edge-decomposition of an n-vertex graph into m edges and t triangles with 2m+3 ≤ n²/2 + o(n²). In this talk, we prove that the only large enough n-vertex graphs that are not decomposable into m edges and t triangles so that 2m+3t ≤ n²/2 are cliques on n=6z+4 vertices.

This is a joint work with A. Blumenthal, B. Lidicky, Y. Pehova, F. Pfender and O. Pikhurko.