Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

3-13-2019

Journal or Book Title

Combinatorics, Probability and Computing

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.

Comments

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.

Copyright Owner

Cambridge University Press

Language

en

File Format

application/pdf

Published Version

Share

COinS