Cichacz–Suchan conjecture on irregular minimum k-critical-bipartite graphs

Let n,mn,m be positive integers such that n>m>1n>m>1, let k=nmk=n-m, and set a=m(k+1)na=\frac{m(k+1)}{n}, which is not an integer. For the bipartite graph G^n,ma\widehat{G}_{n,m}^{\lceil a\rceil} constructed with

U={uii[n]},V={vjj[m]},U=\{u_i\mid i\in[n]\},\qquad V=\{v_j\mid j\in[m]\},

and

E={(ui,v(j+α)modm)i[n], α[a], j=imn},E=\left\{(u_i,v_{(j+\alpha)\bmod m})\mid i\in[n],\ \alpha\in[\lceil a\rceil],\ j=\left\lceil\frac{im}{n}\right\rceil\right\},

Cichacz–Suchan's conjecture. The graph G^n,ma\widehat{G}_{n,m}^{\lceil a\rceil} is kk-critical-bipartite. This means that after the removal of any kk vertices from UU, every vertex in VV can still be matched to a distinct remaining vertex in UU. The conjecture extends the corresponding result for the case in which a=m(k+1)na=\frac{m(k+1)}{n} is an integer to the irregular case.

Sources & referencesView supporting material

Primary source

Sylwia Cichacz, Agieszka Görlich and Karol Suchan, “Minimum k-critical-bipartite graphs: the irregular Case”, arXiv:2307.07315 (2023).

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.