Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture for bipartite cuts
Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture for bipartite cuts
Let be an -vertex graph. A bipartite cut is a cut whose induced subgraph on one side is bipartite. Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture. Any -vertex graph with fewer than edges admits a bipartite cut, while some graphs with edges do not. In particular, . This is the next case after the resolved case ; 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
Sign in to submit a solution.
No solutions have been posted yet.