| Autor: |
KRÁL', DANIEL, LIDICKÝ, BERNARD, MARTINS, TAÍSA L., PEHOVA, YANITSA |
| Předmět: |
|
| Zdroj: |
Combinatorics, Probability & Computing; May2019, Vol. 28 Issue 3, p465-472, 8p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
