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.
References
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.