On the exact decomposition threshold for even cycles

DOI10.1002/JGT.22399zbMATH Open1407.05198arXiv1607.06315OpenAlexW2963907513WikidataQ129128927 ScholiaQ129128927MaRDI QIDQ4629995FDOQ4629995

Authors: Amelia Taylor 

Publication date: 28 March 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A graph $G$ has a $C_k$-decomposition if its edge set can be partitioned into cycles of length $k$. We show that if $delta(G)geq2|G|/3-1$, then $G$ has a $C_4$-decomposition, and if $delta(G)geq|G|/2$, then $G$ has a $C_{2k}$-decomposition, where $kinmathbbN$ and $kgeq4$ (we assume $G$ is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, K"uhn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when $G$ is bipartite or satisfies certain expansion properties.

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

Recommendations

• Decomposing graphs of high minimum degree into 4-cycles
• Decomposing dense bipartite graphs into 4-cycles
• Decompositions of complete multipartite graphs into cycles of even length
• Edge-decompositions of graphs with high minimum degree
• Decompositions of some classes of dense graphs into cycles of lengths 4 and 8

zbMATH Keywords

extremal graph theorygraph decompositioncycle decompositions

Mathematics Subject Classification ID

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

Cited In (6)

• Decomposing graphs of high minimum degree into 4-cycles
• Decomposing dense bipartite graphs into 4-cycles
• Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
• On the decomposition threshold of a given graph
• Minimalist designs
• Cycle decompositions in \(k\)-uniform hypergraphs

This page was built for publication: On the exact decomposition threshold for even cycles

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