Sharp bounds for decomposing graphs into edges and triangles

DOI10.1017/S0963548320000358zbMATH Open1466.05176arXiv1909.11371MaRDI QIDQ4993262FDOQ4993262

Authors: Adam Blumenthal, Bernard Lidický, Yanitsa Pehova, Florian Pfender, Oleg Pikhurko, Jan Volec 

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: For a real constant $alpha$, let $p{i}_3^{a}lpha(G)$ be the minimum of twice the number of $K_2$'s plus $alpha$ times the number of $K_3$'s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $p{i}_3^{a}lpha(n)$ be the maximum of $p{i}_3^{a}lpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $p{i}_3^3(n)$ was first studied by GyH{o}ri 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 $p{i}_3^3(n)le(1/2+o(1))n^2$. We extend their result by determining the exact value of $p{i}_3^{a}lpha(n)$ and the set of extremal graphs for all $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloorn/2floor,lceiln/2ceil}$ are the only possible extremal examples for large $n$.

Full work available at URL: https://arxiv.org/abs/1909.11371

Recommendations

• Decomposing graphs into edges and triangles
• Edge decomposition of complete tripartite graphs
• scientific article; zbMATH DE number 617585
• Edge-decompositions of graphs with high minimum degree
• Fractional triangle decompositions of dense 3-partite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Flag algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient testing of large graphs
• Proof of a conjecture of Katona and Tarjan
• On a problem of G. O. H. Katona and T. Tarján
• On the Decomposition of Graphs
• Edge-decompositions of graphs with high minimum degree
• Title not available (Why is that?)
• On the Minimal Density of Triangles in Graphs
• Title not available (Why is that?)
• The Representation of a Graph by Set Intersections
• Integer and fractional packing of families of graphs
• Integer and fractional packings in dense graphs
• Asymptotic structure of graphs with the minimum number of triangles
• On the number of edge disjoint cliques in graphs of given size
• Fractional triangle decompositions in graphs with large minimum degree
• Decomposing graphs into edges and triangles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of edge-disjoint triangles in \(K_4\)-free graphs
• The exact minimum number of triangles in graphs with given order and size
• On the minimum degree required for a triangle decomposition

Cited In (7)

• Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
• Title not available (Why is that?)
• Sharp bounds for decomposing graphs into edges and triangles
• Decomposing graphs into edges and triangles
• Sharp bounds for decompositions of graphs into completer-partite subgraphs
• Bounds for the decomposition dimension of some class of graphs
• Maximizing five-cycles in \(K_r\)-free graphs

This page was built for publication: Sharp bounds for decomposing graphs into edges and triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993262)