Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

6-6-2018

Journal or Book Title

arxiv

Abstract

We prove the following 30-year old conjecture of Gy˝ori 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˝os, Goodman and Po´sa that asserts the existence of such a decom- position with ℓ ≤ n .

Comments

This is a manuscript made available through arxiv: https://arxiv.org/abs/1710.08486.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS