Article contents
Decomposing Graphs into Edges and Triangles
Published online by Cambridge University Press: 13 March 2019
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 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ős, Goodman and Pósa that asserts the existence of such a decomposition with ℓ ≤ n2/4.
MSC classification
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2019
Footnotes
This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 648509). This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains.
The first author was also supported by the Engineering and Physical Sciences Research Council (EPSRC) Standard Grant EP/M025365/1.
This author was supported in part by NSF grant DMS-1600390.
This author was also supported by the CNPq Science Without Borders grant 200932/2014-4.
References
- 5
- Cited by