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