Decomposing Graphs into Edges and Triangles. (13th March 2019)

• Record Type: Journal Article
• Authors: KRÁL', DANIEL; LIDICKÝ, BERNARD; MARTINS, TAÍSA L.; PEHOVA, YANITSA
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 3(2019)
• Page Start: 465
• Page End: 472
• Publication Date: 2019-03-13
• Subjects: 05C70; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000421
• Languages: English
• ISSNs: 0963-5483

Abstract

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 C 1, . . ., C ℓ of orders two and three such that | C 1 |+···+| C ℓ | ≤ (1/2+ o (1)) n 2 . 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 ℓ ≤ n 2 /4.