The degree-sum conjecture for feasible 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+1|S|\geq 2k+1, and let σ1,1(S)\sigma_{1,1}(S) denote the degree-sum parameter used in the paper. A collection of cycles is SS-kk-feasible when it consists of kk disjoint cycles whose vertices in SS collectively satisfy the required feasibility condition. Degree-sum conjecture. If kk is a positive integer and

σ1,1(S)n+2kS+1,\sigma_{1,1}(S)\geq n+2k-|S|+1,

then GG is SS-kk-feasible. The conjecture proposes a sharp sufficient degree-sum condition for covering specified vertices by disjoint cycles; the examples preceding it show that the bound and the hypothesis S2k+1|S|\geq 2k+1 cannot be lowered in the ways considered there.

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.