The Library
Sharp bounds for decomposing graphs into edges and triangles
Tools
Tools
Tools
Blumenthal, Adam, Lidický, Bernard, Pehova, Yanitsa, Pfende, Florian, Pikhurko, Oleg and Volec, Jan (2021) Sharp bounds for decomposing graphs into edges and triangles. Combinatorics, Probability and Computing, 30 (2). 271 -287. doi:10.1017/S0963548320000358
|
PDF
WRAP-sharp-bounds-for-decomposing-graphs-into-edges-and-triangles-Pikhurko-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (497Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
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) |
Official URL: http://dx.doi.org/10.1017/S0963548320000358
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 | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science > Mathematics | ||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Decomposition (Mathematics), Graph theory, Triangle, Combinatorial analysis | ||||||||||||||||||||||||||||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||||||||||||||||||||||||
| Publisher: | Cambridge University Press | ||||||||||||||||||||||||||||||
| ISSN: | 0963-5483 | ||||||||||||||||||||||||||||||
| Official Date: | March 2021 | ||||||||||||||||||||||||||||||
| Dates: |
|
||||||||||||||||||||||||||||||
| Volume: | 30 | ||||||||||||||||||||||||||||||
| Number: | 2 | ||||||||||||||||||||||||||||||
| Page Range: | 271 -287 | ||||||||||||||||||||||||||||||
| DOI: | 10.1017/S0963548320000358 | ||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||||||||||||||
| Access rights to Published version: | Open Access | ||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||||||||
| Related URLs: | |||||||||||||||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
