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

From papers

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 3n63n-6 edges admits a bipartite cut, while some graphs with 3n63n-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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.