Forest-cut conjecture for sparse graphs

Let GG be a finite, simple, undirected graph of order nn, and call a vertex set a forest cut if it is a vertex cut whose induced subgraph is a forest. Forest-cut conjecture. If GG has less than 3n63n-6 edges, then GG has a forest cut. Maximal planar graphs do not have such vertex cuts, so the density condition would be best possible; the conjecture is verified for planar graphs, and the paper proves the weaker bound that less than 115n185\frac{11}{5}n-\frac{18}{5} edges suffice in general.

Sources & referencesView supporting material

Primary source

Vsevolod Chernyshev, Johannes Rauch and Dieter Rautenbach, “Forest Cuts in Sparse Graphs”, arXiv:2409.17724 (2024).

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.