Article
Decomposing graphs into edges and triangles
Combinatorics, Probability and Computing
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
3-13-2019
DOI
10.1017/S0963548318000421
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.
Copyright Owner
Cambridge University Press
Copyright Date
2019
Language
en
File Format
application/pdf
Citation Information
Daniel Kral, Bernard Lidicky, Taisa L. Martins and Yanitsa Pehova. "Decomposing graphs into edges and triangles" Combinatorics, Probability and Computing (2019) Available at: http://works.bepress.com/bernard-lidicky/44/
This is a manuscript of an an article published as D. Král', B. Lidický, T. L. Martins, Y. Pehova. Decomposing Graphs into Edges and Triangles. Combinatorics, Probability and Computing (2019), doi: 10.1017/S0963548318000421. Posted with permission.