Kostochka et al.'s super-neighborhood cycle conjecture for bigraphs

A bigraph is a bipartite graph G=(X,Y)G=(X,Y) with an ordered vertex partition. For a set SXS\subseteq X, let Λ2(S)\mathsf{\Lambda}^2(S) be the vertices adjacent to at least two vertices of SS. The graph is snp if, for every SXS\subseteq X with S3|S|\geq 3, Λ2(S)S|\mathsf{\Lambda}^2(S)|\geq |S| and G[SΛ2(S)]G[S\cup\mathsf{\Lambda}^2(S)] is 22-connected.

Kostochka et al.'s conjecture. If a bigraph G=(X,Y)G=(X,Y) is snp, then there is a cycle containing all vertices of XX.

This is the graph-theoretic form of the conjectured equivalence between the super-neighborhood property and super-pancyclicity of hypergraphs. The conjecture is known for X{3,4,5,6,7}|X|\in\{3,4,5,6,7\}, while the general case remains open.

Sources & referencesView supporting material

Primary source

Guantao Chen, Mikhail Lavrov, Yuying Ma, Yimo Su and Jennifer Vandenbussche, “Bipartite graphs with the double Hall property”, arXiv:2502.10903 (2025).

Additional references

2 papers in this index state this conjecture (2023–2025). The statement above is taken from the most recent of them; the others are arXiv:2310.05248.

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.