Decomposing graphs into edges and triangles

DOI10.1017/S0963548318000421zbMATH Open1436.05086arXiv1710.08486MaRDI QIDQ5222546FDOQ5222546

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)

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$.

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

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

zbMATH Keywords

complete graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)