Decomposing Graphs into Edges and Triangles

KRÁĽ, Daniel, B LIDICKY, TL MARTINS and Y PEHOVA. Decomposing Graphs into Edges and Triangles. COMBINATORICS PROBABILITY & COMPUTING. NEW YORK: CAMBRIDGE UNIV PRESS, 2019, vol. 28, No 3, p. 465-472. ISSN 0963-5483. Available from: https://dx.doi.org/10.1017/S0963548318000421.

Basic information

Original name

Decomposing Graphs into Edges and Triangles

Authors

KRÁĽ, Daniel, B LIDICKY, TL MARTINS and Y PEHOVA

Edition

COMBINATORICS PROBABILITY & COMPUTING, NEW YORK, CAMBRIDGE UNIV PRESS, 2019, 0963-5483

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.879

DOI

http://dx.doi.org/10.1017/S0963548318000421

UT WoS

000462848800006

---

Abstract

V originále

We prove the following 30 year-old conjecture of Gyori and Tuza: the edges of every n-vertex graph G can be decomposed into complete graphs C-1, ..., C-l of orders two and three such that vertical bar C-1 vertical bar+ ... + vertical bar C-l vertical bar (1/2 + o(1))n(2). This result implies the asymptotic version of the old result of Erdos, Goodman and POsa that asserts the existence of such a decomposition with l <= n(2)/4.