Journal or Book Title
We prove the following 30-year old conjecture of Gy˝ori and Tuza: the edges of every n-vertex graph G can be decomposed into complete graphs C1, . . . , Cℓ of orders two and three such that |C1| + · · · + |Cℓ| ≤ (1/2 + o(1))n2. This result implies the asymptotic version of the old result of Erd˝os, Goodman and Po´sa that asserts the existence of such a decom- position with ℓ ≤ n .
Kral, Daniel; Lidicky, Bernard; Martins, Taisa L.; and Pehova, Yanitsa, "Decomposing graphs into edges and triangles" (2018). Mathematics Publications. 177.