Chernyshev–Rauch–Rautenbach conjecture on sparse graphs and forest cuts

Let GG be a graph of order nn, and let a forest cut mean a vertex cut MM such that the subgraph GMG|_M induced by the cut vertices is a forest.

Chernyshev–Rauch–Rautenbach conjecture. If GG has fewer than 3n63n-6 edges, then GG has a forest cut.

The conjecture is known for planar graphs, while the paper improves previously proved linear edge bounds to fewer than (19n28)/8(19n-28)/8 edges; the sharp threshold 3n63n-6 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

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.