pith. sign in

arxiv: 1607.06315 · v1 · pith:MR3NIER2new · submitted 2016-07-21 · 🧮 math.CO

On the exact decomposition threshold for even cycles

classification 🧮 math.CO
keywords decompositionasymptoticcyclesdeltaexactresultssatisfiesthen
0
0 comments X
read the original 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)\geq 2|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 $k\in \mathbb{N}$ and $k\geq 4$ (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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.