2025/11/13 by Samuel J Schneider, Schneider, Samuel, Torsten Ueckerdt +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2511.10717
openalex publication_date 2025/11/13 · openalex created_date 2025/11/18 · openalex updated_date 2026/07/28
Chernyshev, Rauch and Rautenbach [Discrete Math., 2025] introduce forest cuts, i.e., vertex separators that induce a forest. They conjecture that, similar to a result by Chen and Yu [Discrete Math., 2002], every n-vertex graph with less than 3n-6 edges has a forest cut. As an intermediate goal they ask how many edges an n-vertex 3-connected graph must have such that the neighborhood of every vertex contains a cycle. Li, Tang and Zhan [arXiv, 2024] resolve this problem by showing that every such graph has at least 15n/8 edges, while there are examples of such graphs with exactly 15n/8 edges. We give a much shorter proof for this.