부산대학교 도서관

Let π3(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 π3(n), the maximum of π³(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 π3(n) ≥ 9n²=16. In a recent advance on this problem, Kríl', Lidický, Martins and Pehova [arXiv:1710:08486] proved via ag algebras that π3(n) ≥ (1=2 + o(1))n², which is tight up to the o(1) term. We extend their proof by giving the exact value of π3(n) for large n, and we show that Kn and Kb{n/2},[n/2] are the only extremal examples. [ABSTRACT FROM AUTHOR]