# Sharp bounds for decomposing graphs into edges and triangles

## Main Article Content

## Abstract

Let pi3(G) be the minimum of twice the number of edges plus three times the number of triangles over all edge-decompositions of G into copies of K2 and K3. We are interested in the value of pi3(n), the maximum of pi3(G) over graphs G with n vertices. This specific extremal function was first studied by Gyori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320], who showed that pi3(n)<9n2/16.

In a recent advance on this problem, Kral, Lidicky, Martins and Pehova [arXiv:1710:08486] proved via flag algebras that pi3(n)<(1/2+o(1))n2, which is tight up to the o(1) term.

We extend their proof by giving the exact value of pi3(n) for large n, and we show that Kn and Kn/2,n/2 are the only extremal examples.

In a recent advance on this problem, Kral, Lidicky, Martins and Pehova [arXiv:1710:08486] proved via flag algebras that pi3(n)<(1/2+o(1))n2, which is tight up to the o(1) term.

We extend their proof by giving the exact value of pi3(n) for large n, and we show that Kn and Kn/2,n/2 are the only extremal examples.

## Article Details

How to Cite

Blumenthal, A., Lidický, B., Pikhurko, O., Pehova, Y., Pfender, F., & Volec, J.
(2019).
Sharp bounds for decomposing graphs into edges and triangles.

*Acta Mathematica Universitatis Comenianae, 88*(3), 463-468. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1191/681
Issue

Section

EUROCOMB 2019