On the exact decomposition threshold for even cycles
classification
🧮 math.CO
keywords
decompositionasymptoticcyclesdeltaexactresultssatisfiesthen
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.