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

About 3 years old · traced to

A bigraph is a bipartite graph G=(X,Y)G=(X,Y) with an ordered vertex partition. For a set S⊆XS\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 S⊆XS\subseteq X with ∣S∣≥3|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.

References

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.