Chernyshev–Rauch–Rautenbach conjecture on sparse graphs and forest cuts
Let be a graph of order , and let a forest cut mean a vertex cut such that the subgraph induced by the cut vertices is a forest.
Chernyshev–Rauch–Rautenbach conjecture. If has fewer than edges, then has a forest cut.
The conjecture is known for planar graphs, while the paper improves previously proved linear edge bounds to fewer than edges; the sharp threshold remains unresolved in general.
References
Primary source
Ilya I. Bogdanov, Elizaveta Neustroeva, Georgy Sokolov, Alexei Volostnov, Nikolay Russkin and Vsevolod Voronov, “On forest and bipartite cuts in sparse graphs”, arXiv:2505.16179 (2025).
Additional references
2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2411.17885.
Progress summary
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.