The Library
Decomposing graphs into edges and triangles
Tools
Tools
Tools
Králʼ, Daniel, Lidicky, Bernard, Martins, Taisa and Pehova, Yanitsa (2019) Decomposing graphs into edges and triangles. Combinatorics, Probability and Computing, 28 (3). pp. 465-472. doi:10.1017/S0963548318000421 ISSN 0963-5483.
|
PDF
WRAP-decomposing-graphs-edges-triangles-Kral-2018.pdf - Accepted Version - Requires a PDF viewer. Download (434Kb) | Preview |
Official URL: https://doi.org/10.1017/S0963548318000421
Abstract
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||
| Publisher: | Cambridge University Press | ||||||||
| ISSN: | 0963-5483 | ||||||||
| Official Date: | May 2019 | ||||||||
| Dates: |
|
||||||||
| Volume: | 28 | ||||||||
| Number: | 3 | ||||||||
| Page Range: | pp. 465-472 | ||||||||
| DOI: | 10.1017/S0963548318000421 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | This article has been published in a revised form in Combinatorics, Probability and Computing https://doi.org/10.1017/S0963548318000421. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © copyright holder. | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Copyright Holders: | © Cambridge University Press 2019 | ||||||||
| Date of first compliant deposit: | 7 June 2018 | ||||||||
| Date of first compliant Open Access: | 13 September 2019 | ||||||||
| Related URLs: | |||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
