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

Let KknK_k^n be the complete kk-partite graph with nn vertices in each part, let CC_{\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 >k3\ell>k\geq 3, 6\ell\geq 6, and sufficiently large nn,

sat(Kkn,C)=kn+1+222+2(1222)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.

Sources & referencesView supporting material

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.