Extremal structure for saturation by cycles of length at least ℓ\ell

At least 1 year old · documented by

Let KknK_k^n be the complete kk-partite graph with nn vertices in each part, let C≥ℓC_{\geq\ell} be the family of cycles of length at least ℓ\ell, and let Ω(ℓ,k,n)\Omega^{(\ell,k,n)} be the graph family defined in the paper. Long-cycle partite saturation conjecture. For ℓ>k≥3\ell>k\geq 3, ℓ≥6\ell\geq 6, and sufficiently large nn,

sat(Kkn,C≥ℓ)=kn−ℓ+1+⌊ℓ−22⌋2+2(ℓ−1−2⌊ℓ−22⌋)⌊ℓ−22⌋,sat(K_k^n,C_{\geq\ell})=kn-\ell+1+\left\lfloor\frac{\ell-2}{2}\right\rfloor^2+2\left(\ell-1-2\left\lfloor\frac{\ell-2}{2}\right\rfloor\right)\left\lfloor\frac{\ell-2}{2}\right\rfloor,

and all extremal graphs belong to Ω(ℓ,k,n)\Omega^{(\ell,k,n)}. The conjecture proposes both an exact saturation number and a complete description of the extremal graphs; the supplied text provides no resolution evidence.

References

Primary source

Yiduo Xu, Zhen He and Mei Lu, “Partite saturation number of cycles”, arXiv:2410.11194 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.