Decomposing graphs into edges and triangles

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,\dots ,C_{\ell }$ of orders two and three such that $|C_1|+\cdots +|C_{\ell }|\le (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 $\ell \le n^2/4$.

We present a shorter proof of our main result; the original proof, which can be of independent interest, is contained in versions 1 and 2 of the manuscript. Small fixes suggested by the referee

References in corpus (4)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• Crossing numbers of complete tripartite and balanced complete multipartite graphs

Cited by in corpus (2)

• $C_5$ is almost a fractalizer
• Spectral radius and clique partitions of graphs