Forest-cut conjecture for sparse graphs
Forest-cut conjecture for sparse graphs
Let be a finite, simple, undirected graph of order , and call a vertex set a forest cut if it is a vertex cut whose induced subgraph is a forest. Forest-cut conjecture. If has less than edges, then 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 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
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.