PreprintarXiv licencearXiv
Even cycle decomposition thresholds for dense multipartite graphs
Abstract
Let r≥ 2 be an integer. An r-partite graph Γ with vertex partition V1,…,Vr is $2$-balanced if there exists a positive integer n such that n≤ |Vi|≤ 2n for every i∈[r]. For an integer ℓ≥3, let Cℓ denote the cycle of length ℓ, and define δ̂(Γ)=min{dΓ(v,Vi)/|Vi|:i∈[r], v∈ V(Γ)∖ Vi}. Let δ̂rCℓ denote the Cℓ-decomposition threshold for $2$-balanced r-partite graphs, that is, the least nonnegative real number δ such that, for every ε>0, there exists n0 such that every Cℓ-divisible $2$-balanced r-partite graph G with mini|Vi|>n0 and δ̂(G)≥δ+ε admits a Cℓ-decomposition. We prove that δ̂rC4=2/3 and δ̂rC2k=1/2 for every r≥2 and every k≥3.
Related
- Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs
- Chromatic Extremal Thresholds and the Multipartite K4-Free Problem
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- An e-positive classification for complete multipartite graphs
- On decomposition thresholds for odd cycles
BibTeX
@misc{sun2026even,
title = {{Even cycle decomposition thresholds for dense multipartite graphs}},
author = {Weiyi Sun and Tao Feng and Shikang Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04890},
eprint = {2610.04890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04890},
}
RIS
TY - UNPB
TI - Even cycle decomposition thresholds for dense multipartite graphs
AU - Weiyi Sun
AU - Tao Feng
AU - Shikang Yu
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04890
UR - https://arxiv.org/abs/2610.04890
AB - Let r≥ 2 be an integer. An r-partite graph Γ with vertex partition V_1,…,V_r is $2$-balanced if there exists a positive integer n such that n≤ |V_i|≤ 2n for every i∈[r]. For an integer ℓ≥3, let C_ℓ denote the cycle of length ℓ, and define δ̂(Γ)=min{d_Γ(v,V_i)/|V_i|:i∈[r], v∈ V(Γ)∖ V_i}. Let δ̂^r_C_ℓ denote the C_ℓ-decomposition threshold for $2$-balanced r-partite graphs, that is, the least nonnegative real number δ such that, for every ε>0, there exists n_0 such that every C_ℓ-divisible $2$-balanced r-partite graph G with min_i|V_i|>n_0 and δ̂(G)≥δ+ε admits a C_ℓ-decomposition. We prove that δ̂^r_C_4=2/3 and δ̂^r_C_2k=1/2 for every r≥2 and every k≥3.
ER -