The prescribed partition conjecture for disjoint cycles in bipartite graphs

Let G[X,Y]G[X,Y] be a balanced bipartite graph of order 2n2n, let SS be a subset of XX with S2k+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,ni2(1ik),|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 1ik.|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.

Sources & referencesView supporting material

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.