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$.

arXiv commentWe 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 (9)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Non-three-colorable common graphs exist
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• A Note on the Inducibility of 4-vertex Graphs
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• A new lower bound based on Gromov's method of selecting heavily covered points
• Counting flags in triangle-free digraphs
• 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