Publication details
Decomposing Graphs into Edges and Triangles
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Periodical |
| Magazine / Source | COMBINATORICS PROBABILITY & COMPUTING |
| Citation | |
| Doi | http://dx.doi.org/10.1017/S0963548318000421 |
| Description | 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. |