Campus Units

Mathematics

Document Type

Abstract

Conference

EUROCOMB 2019

Publication Version

Published Version

Publication Date

2019

Journal or Book Title

Acta Mathematica Universitatis Comenianae

Volume

88

Issue

3

First Page

463

Last Page

468

Conference Title

EUROCOMB 2019

Conference Date

August 26-30, 2019

City

Bratislava, Slovakia

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.

Comments

This abstract is published as 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. Posted with permission.

Copyright Owner

Acta Mathematica Universitatis Comenianae

Language

en

File Format

application/pdf

Share

Article Location

 
COinS