Decomposing Graphs into Edges and Triangles. (13th March 2019) - KRÁL', DANIEL; LIDICKÝ, BERNARD; MARTINS, TAÍSA L.; PEHOVA, YANITSA
Abstract : We prove the following 30 year-old conjecture of Győri and Tuza: the edges of every n -vertex graph G can be decomposed into complete graphs C 1, . . ., C ℓ of orders two and three such that | C 1 |+···+| C ℓ | ≤ (1/2+ o (1)) n 2 . This result implies the asymptotic version of the old result of Erdős, Goodman and Pósa that asserts the existence of such a decomposition with ℓ ≤ n 2 /4.