Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture for bipartite cuts

Let GG be an nn-vertex graph. A bipartite cut is a cut whose induced subgraph on one side is bipartite. Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture. Any nn-vertex graph with fewer than 3n−63n-6 edges admits a bipartite cut, while some graphs with 3n−63n-6 edges do not. In particular, ℓ3=3\ell_3=3. This is the next case after the resolved case ℓ2=2\ell_2=2; the conjecture is open, with partial progress on related forest-cut and bipartite-cut bounds.

References

Primary source

Guillaume Aubian, Marthe Bonamy, Romain Bourneuf, Oscar Fontaine and Lucas Picasarri-Arrieta, “On cuts of small chromatic number in sparse graphs”, arXiv:2510.01791 (2025).

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.