Decomposing graphs into edges and triangles

DOI10.1017/S0963548318000421MaRDI QIDQ5222546zbMATH OpenFDO

Authors Bernard Lidický, Taísa L. Martins, Yanitsa Pehova, Daniel Král'

Publication date 6 April 2020

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

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

zbMATH Keywords

complete graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove the following 30-year old conjecture of GyH{o}ri and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,ldots,C_{e}ll$ of orders two and three such that $|C_1|+cdots+|C_{e}ll|le(1/2+o(1))n^2$. This result implies the asymptotic version of the old result of ErdH{o}s, Goodman and P'osa that asserts the existence of such a decomposition with $ellle{n}^2/4$.

Recommendations

• Sharp bounds for decomposing graphs into edges and triangles
• Decomposing random graphs into few cycles and edges
• Decompositions of complete graphs into triangles and Hamilton cycles
• On a Conjecture of Erdős, Gallai, and Tuza
• scientific article; zbMATH DE number 617585

Cites work

• scientific article; zbMATH DE number 4196017 (Why is no real title available?)
• A Solution to the 2/3 Conjecture
• A blow-up lemma for approximate decompositions
• A new bound for the 2/3 conjecture
• A new lower bound based on Gromov's method of selecting heavily covered points
• A note on the inducibility of 4-vertex graphs
• A problem of Erdős on the minimum number of \(k\)-cliques
• Decomposing graphs into edges and triangles
• Flag algebras
• Greedy maximum-clique decompositions
• Hypergraphs do jump
• Integer and fractional packing of families of graphs
• Integer and fractional packings in dense graphs
• Limits of order types
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Monochromatic triangles in three-coloured graphs
• Non-three-colourable common graphs exist
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• On the Decomposition of Graphs
• On the density of transitive tournaments
• On the number of edge-disjoint triangles in \(K_4\)-free graphs
• Proof of a conjecture of Katona and Tarjan
• Quasirandom permutations are characterized by 4-point densities
• Rainbow triangles in three-colored graphs
• Semidefinite programming and Ramsey numbers
• The Representation of a Graph by Set Intersections
• The codegree threshold for 3-graphs with independent neighborhoods
• The greedy clique decomposition of a graph
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Cited in

(13)

• Sharp bounds for decomposing graphs into edges and triangles
• Towards the Erdős-Gallai cycle decomposition conjecture
• Sharp bounds for decomposing graphs into edges and triangles
• An overview of graph covering and partitioning
• Decomposing toroidal graphs into circuits and edges
• Spectral radius and clique partitions of graphs
• Eigenvalues and clique partitions of graphs
• Decomposing graphs into edges and triangles
• A Short proof of the blow-up lemma for approximate decompositions
• Graph and hypergraph packing
• Compactness and finite forcibility of graphons
• C5 ${C}_{5}$ is almost a fractalizer
• More on decompositions of edge-colored complete graphs

This page was built for publication: 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 Q5222546)