Chernyshev–Rauch–Rautenbach conjecture on sparse graphs and forest cuts
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.