The prescribed partition conjecture for disjoint cycles in bipartite graphs

About 6 years old · traced to

Let G[X,Y]G[X,Y] be a balanced bipartite graph of order 2n2n, let SS be a subset of XX with ∣S∣≥2k+2|S|\geq 2k+2, and let SCiS_{C_i} denote the vertices of SS on a cycle CiC_i. Prescribed partition conjecture. If

σ1,1(S)≥n+2,\sigma_{1,1}(S)\geq n+2,

then for any integer partition

∣S∣=n1+⋯+nk,ni≥2(1≤i≤k),|S|=n_1+\cdots+n_k,\qquad n_i\geq 2\quad(1\leq i\leq k),

there are kk disjoint cycles C1,…,CkC_1,\ldots,C_k such that

∣SCi∣=nifor all 1≤i≤k.|S_{C_i}|=n_i\quad\text{for all }1\leq i\leq k.

This is a stronger prescribed-distribution version of the cycle-covering problem: the degree-sum condition is required to realize every partition of the specified vertices into admissible cycle sizes. The supplied text gives no resolution, so the conjecture remains open.

References

Primary source

Suyun Jiang and Jin Yan, “Disjoint cycles covering specified vertices in bipartite graphs with partial degrees”, arXiv:2011.10791 (2020).

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.