Decomposing Graphs into Edges and Triangles

KRÁĽ, Daniel, B LIDICKY, TL MARTINS a Y PEHOVA. Decomposing Graphs into Edges and Triangles. COMBINATORICS PROBABILITY & COMPUTING. NEW YORK: CAMBRIDGE UNIV PRESS, 2019, roč. 28, č. 3, s. 465-472. ISSN 0963-5483. Dostupné z: https://dx.doi.org/10.1017/S0963548318000421.

Základní údaje

Originální název

Decomposing Graphs into Edges and Triangles

Autoři

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

Vydání

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

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

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

Impakt faktor

Impact factor: 0.879

DOI

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

UT WoS

000462848800006

---

Anotace

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.