Blumenthal, Adam, Lidický, Bernard, Pehova, Yanitsa, Pfende, Florian, Pikhurko, Oleg and Volec, Jan (2020) Sharp bounds for decomposing graphs into edges and triangles. Combinatorics, Probability and Computing . (In Press)

PDF WRAP-sharp-bounds-decomposing-graphs-edges-triangles-Pikhurko-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1062Kb)

Request Changes to record.

Abstract

For a real constant α, let π α 3 (G) be the minimum of twice the number of K2’s plus α times the number of K3’s over all edge decompositions of G into copies of K2 and K3, where Kr denotes the complete graph on r vertices. Let π α 3 (n) be the maximum of π α 3 (G) over all graphs G with n vertices. The extremal function π 3 3 (n) was first studied by Gy˝ori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315– 320]. In a recent progress on this problem, Kr´al’, Lidick´y, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465–472] proved via flag algebras that π 3 3 (n) 6 (1/2+o(1))n 2 . We extend their result by determining the exact value of π α 3 (n) and the set of extremal graphs for all α and sufficiently large n. In particular, we show for α = 3 that Kn and the complete bipartite graph K⌊n/2⌋,⌈n/2⌉ are the only possible extremal examples for large n.

Item Type:	Journal Article
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Combinatorics, Probability and Computing
Publisher:	Cambridge University Press
ISSN:	0963-5483
Official Date:	4 June 2020
Dates:	Date Event 4 June 2020 Accepted
Date of first compliant deposit:	3 August 2020
Status:	Peer Reviewed
Publication Status:	In Press
Access rights to Published version:	Restricted or Subscription Access
Related URLs:	Publisher
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item